tags: 練習題

Dynamic Programming

1143. Longest Common Subsequence(Medium)

限制 :

1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.

Solution

利用 Dynamic programming 計算最長子序列。

1. 利用前面的結果推後面的結果
2. 減少計算量

演算法:

1. 建立一個從 text1 –> text2 的表格，如下圖所示:

   LCS	""	text2[0]	text2[1]	…	…	text2[0]
   ""
   text1[0]
   text1[1]
   …
   …
   text1[text1.size()-1]

2. 比較 text1[m] 和 text2[n] 是否相同

   1. 如果相同 : 看看 看看 m 和 n 是不是邊界，不是邊界就拿 text1[m]、text2[n]的值 +1。
   2. 反之: max(i > 0 ? record[i-1][j] : 0, j > 0 ? record[i][j-1] : 0)

時間複雜度:

$O(text1\ast text2)$

空間複雜度:

$O(text1\ast text2)$

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<short>> record(text1.size()+1, vector<short>(text2.size() + 1));
        for(int i = 0; i < record.size(); i++)            record[i][0] = 0;
        for(int i = 0; i < record[0].size(); i++)         record[0][i] = 0;

        for(int i = 0; i < text1.size(); i++)
        {
            for(int j = 0; j < text2.size(); j++)
            {
                if(text1[i] == text2[j])
                {
                    record[i][j] = (i && j ? record[i-1][j-1] : 0) + 1;
                }
                else
                {
                    record[i][j] = max(i > 0 ? record[i-1][j] : 0, j > 0 ? record[i][j-1] : 0);
                }
            }
        }
        return record[text1.size()-1][text2.size()-1];
    }
};

reference : link