利用二维数组保存匹配情况


  • 0
    X
    class Solution {
    public:
    int findLength(vector<int>& A, vector<int>& B) {
        
        int max_repeat_len = DP_Array(A, B);  
        
        // 朴素思想
        // for (int i = 0; i < A.size(); i++) {
        //     for (int j = 0; j < B.size(); j++) {
        //         // if (A[i] == B[j]) {
        //         //     int repeat = 0;
        //         //     for (int k = i, t = j; k < A.size() && t < B.size(); ) {
        //         //         if (A[k] == B[t]) {
        //         //             repeat++;
        //         //             k++;
        //         //             t++;
        //         //         } else {
        //         //             break;
        //         //         }
        //         //     }
        //         //     max_repeat_len = max_repeat_len >= repeat ? max_repeat_len: repeat;
        //         //  }        
        //     }
        // }
        
        return max_repeat_len;
    }
    
    int DP_Matrix(vector<int>& A, vector<int>& B) {
        int max_repeat_len = 0;
        vector<vector<int> > dp(A.size() + 1, vector<int>(B.size() + 1));
        
        for (int i = 0; i < A.size(); i++) {
            for (int j = 0; j < B.size(); j++) {
    
                if (A[i] == B[j])
                    max_repeat_len = max(max_repeat_len, dp[i+1][j+1] = dp[i][j] + 1);
            }
        }
        return max_repeat_len;
    }
    
    int DP_Array(vector<int>& A, vector<int>& B) {
        int max_repeat_len = 0;
        vector<int> dp(B.size() + 1);
        
        for (int i = A.size() - 1; i >= 0; i--) {
            for (int j = 0; j < B.size(); j++) {
    
                max_repeat_len = max(max_repeat_len, dp[j] = A[i] == B[j] ? dp[j + 1] + 1: 0);  // dp[j+1]为上一次匹配相邻字符的匹配情况
            }
        }
        return max_repeat_len;
    }
    };
    
    /*
    应用了动态规划中最长公共子序列的思想,做一个二维数组,数组的每个元素所在位置对应两个字符在两个待匹配字符串的位置,值为其所在位置匹配的子串长度
    
    可以将二维数组变成一维数组,思想不变,只是重复遍历并更改一维数组的每个元素,每一次遍历以上一次遍历结果为初始值,对每一个元素都进行更改(在两个元素不等时要将当前位置元素置为0)
    */

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.