'''Description
Given two strings, find the longest common subsequence (LCS).

Your code should return the length of LCS.

Have you met this question in a real interview? 
Clarification
What's the definition of Longest Common Subsequence?

https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
http://baike.baidu.com/view/2020307.htm
Example
For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.

For "ABCD" and "EACB", the LCS is "AC", return 2.
'''
class Solution:
    """
    @param A, B: Two strings.
    @return: The length of longest common subsequence of A and B.
    """
    def longestCommonSubsequence(self, A, B):
        # write your code here
        if not A or not B:
            return 0
            
        m, n = len(A), len(B)
        # f[i][j]: find the lcs in A[0:i+1] and B[0:j+1]
        f = [[0] * (n) for i in range(m)]
        # initialize row 0 and column 0
        for i in xrange(m):
            if A[i] == B[0]:
                f[i][0] = 1
        for j in xrange(n):
            if B[j] == A[0]: 
                f[0][j] = 1
        
        for i in range(1,m):
            for j in range(1,n):
                # Calculate f[i][j] based on state transfer equation
                f[i][j] = max(f[i - 1][j], f[i][j - 1])
                if A[i] == B[j]:
                    f[i][j] = f[i - 1][j - 1] + 1
        # return ans
        return f[m - 1][n - 1]
'''Summary
http://www.cnblogs.com/en-heng/p/3963803.html

http://www.cnblogs.com/ider/p/longest-common-substring-problem-optimization.html

最长公共子串(Longest Common Substring)是一个非常经典的面试题目，在实际的程序中也有很高的实用价值，所以把该问题的解法总结在本文重。不过不单单只是写出该问题的基本解决代码而已，关键还是享受把学习算法一步步的优化，让时间和空间复杂度一步步的减少的惊喜。

概览
最长公共子串问题的基本表述为：

给定两个字符串，求出它们之间最长的相同子字符串的长度。

最直接的解法自然是找出两个字符串的所有子字符串进行比较看他们是否相同，然后取得相同最长的那个。对于一个长度为n的字符串，它有n(n+1)/2 个非空子串。所以假如两个字符串的长度同为n，通过比较各个子串其算法复杂度大致为O(n4)。这还没有考虑字符串比较所需的时间。简单想想其实并不需要取出所有的子串，而只要考虑每个子串的开始位置就可以，这样可以把复杂度减到O(n3)。

但这个问题最好的解决办法是动态规划法，在后边会更加详细介绍这个问题使用动态规划法的契机：有重叠的子问题。进而可以通过空间换时间，让复杂度优化到O(n2)，代价是空间复杂度从O(1)一下子提到了O(n2)。

从时间复杂度的角度讲，对于最长公共子串问题，O(n2)已经是目前我所知最优的了，也是面试时所期望达到的。但是对于空间复杂度O(n2)并不算什么，毕竟算法上时间比空间更重要，但是如果可以省下一些空间那这个算法就会变得更加美好。所以进一步的可以把空间复杂度减少到O(n)，这是相当美好了。但有一天无意间让我发现了一个算法可以让该问题的空间复杂度减少回原来的O(1)，而时间上如果幸运还可以等于O(n)。

暴力解法 – 所得即所求
对于该问题，直观的思路就是问题要求什么就找出什么。要子串，就找子串；要相同，就比较每个字符；要最长就记录最长。所以很容易就可以想到如下的解法。

该解法的思路就如前所说，以字符串中的每个字符作为子串的端点，判定以此为开始的子串的相同字符最长能达到的长度。其实从表层上想，这个算法的复杂度应该只有O(n2)因为该算法把每个字符都成对相互比较一遍，但关键问题在于比较两个字符串的效率并非是O(1)，这也导致了实际的时间复杂度应该是满足Ω(n2)和O(n3)。

动态规划法 – 空间换时间
有了一个解决问题的方法是一件很不错的事情了，但是拿着上边的解法回答面试题肯定不会得到许可，面试官还是会问有没有更好的解法呢？不过上述解法虽然不是最优的，但是依然可以从中找到一个改进的线索。不难发现在子串比较中有很多次重复的比较。

比如再比较以i和j分别为起始点字符串时，有可能会进行i+1和j+1以及i+2和j+2位置的字符的比较；而在比较i+1和j+1分别为起始点字符串时，这些字符又会被比较一次了。也就是说该问题有非常相似的子问题，而子问题之间又有重叠，这就给动态规划法的应该提供了契机。

暴力解法是从字符串开端开始找寻，现在换个思维考虑以字符结尾的子串来利用动态规划法。

假设两个字符串分别为s和t，s[i]和t[j]分别表示其第i和第j个字符(字符顺序从0开始)，再令L[i, j]表示以s[i]和s[j]为结尾的相同子串的最大长度。应该不难递推出L[i, j]和L[i+1,j+1]之间的关系，因为两者其实只差s[i+1]和t[j+1]这一对字符。若s[i+1]和t[j+1]不同，那么L[i+1, j+1]自然应该是0，因为任何以它们为结尾的子串都不可能完全相同；而如果s[i+1]和t[j+1]相同，那么就只要在以s[i]和t[j]结尾的最长相同子串之后分别添上这两个字符即可，这样就可以让长度增加一位。合并上述两种情况，也就得到L[i+1,j+1]=(s[i]==t[j]?L[i,j]+1:0)这样的关系。

最后就是要小心的就是临界位置：如若两个字符串中任何一个是空串，那么最长公共子串的长度只能是0；当i为0时，L[0,j]应该是等于L[-1,j-1]再加上s[0]和t[j]提供的值，但L[-1,j-1]本是无效，但可以视s[-1]是空字符也就变成了前面一种临界情况，这样就可知L[-1,j-1]==0，所以L[0,j]=(s[0]==t[j]?1:0)。对于j为0也是一样的，同样可得L[i,0]=(s[i]==t[0]?1:0)。

算法开辟了一个矩阵内存来存储值来保留计算值，从而避免了重复计算，于是运算的时间复杂度也就降至了O(n2)。

动态规划法优化 – 能省一点是一点
仔细回顾之前的代码，其实可以做一些合并让代码变得更加简洁，比如最后一个求最长的嵌套for循环其实可以合并到之前计算整个表的for循环之中，每计算完L[i,j]就检查它是的值是不是更长。当合并代码之后，就会发现内部循环的过程重其实只用到了整个表的相邻两行而已，对于其它已经计算好的行之后就再也不会用到，而未计算的行曽之前也不会用到，因此考虑只用两行来存储计算值可能就足够。

跟之前的动态规划算法代码相比，两种解法并没有实质的区别，完全相同的嵌套for循环，只是将检查最长的代码也并入其中，然后table中所拥有的行也只剩下2个。

此解法的一些技巧在于如何交换两个行数组作为工作数组。可以交换数组中的每个元素，异或交换一对指针。上边代码中所用的方法类似于后者，根据奇偶性来决定那行数组可以被覆盖，哪行数组有需要的缓存数据。不管怎么说，该算法都让空间复杂度从O(n2)减少到了O(n)，相当有效。

动态规划法再优化 – 能用一点就只用一点
最长公共子串问题的解法优化到之前的模样，基本是差不多了，Wikipedia上对于这个问题给出的解法也就到上述而已。但思考角度不同，还是有意外的惊喜的。不过要保持算法的时间复杂度不增加，算法的基本思路方针还是不能变的。
'''