718. Maximum Length of Repeated Subarray

這題的題目要我們在兩個陣列中, 找到相等最大的子陣列

怎麼找呢, 最暴力的方式就是, 先固定其中一個陣列(A), 開始遍歷他

然後從另一個陣列(B)的每個index開始找, 是否有連續段, 有的話就是做到連續段掉, 就是跑到(B)的連續段掉, B就是換到下個index

做完之後, 兩邊反過來再做一次

有個疑問, 為什麼不在一個為什麼一次做完就好了, 幹嘛做兩次,

因為當data太大時間會太長, 所以我覺得兩邊顛倒在做一次這做法蠻聰明的,

就不用去計算所有陣列的可能, 而是假設真的有誤會我們從另一邊看也一定找得出來

算是很聰明的暴力法, 不然一般的暴力法會TLE (O(n²))

這個方法相當於O(m * min(m, n))

class Solution {
  public:
    int findLength(vector<int> &A, vector<int> &B) {
        int Ap = 0;
        int Bp = 0;
        int max_length = 0;
        int m = A.size();
        int n = B.size();
for (int offset = 0; offset < m; ++offset) {
            for (int i = offset, j = 0; i < m && j < n;) {
                int count = 0;
                while (i < m && j < n && A[i++] == B[j++])
                    count++;
                max_length = max(max_length, count);
            }
        }
        for (int offset = 0; offset < n; ++offset) {
            for (int i = offset, j = 0; i < m && j < n;) {
                int count = 0;
                while (i < m && j < n && B[i++] == A[j++])
                    count++;
                max_length = max(max_length, count);
            }
        }
        return max_length;
    }
};

另一個就是dp

我們紀錄A的前i個跟B的前j個的最大長度子串列

若A[i]== B[j], 則上一個dp[i -1][j -1] + 1, 反之就壞了 直接設0

要注意邊界的case

class Solution {
  public:
    int findLength(vector<int> &A, vector<int> &B) {
        vector<vector<int>> dp(A.size(), vector<int>(B.size(), 0));
        int res = 0;
        for (int i = 0; i < A.size(); i++) {
            for (int j = 0; j < B.size(); j++) {
                if (i == 0 || j == 0) {
                    if (A[i] == B[j]) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = 0;
                    }
                } else {
                    if (A[i] == B[j]) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = 0;
                    }
                }
                res = max(res, dp[i][j]);
            }
        }
        return res;
    }
};

有個比較精簡的寫法, 簡單來說就是把原本i,j的結果都往後紀錄, 可以不用寫這麼多判別式

class Solution {
  public:
    int findLength(vector<int> &A, vector<int> &B) {
        vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));
        int res = 0;
        for (int i = 1; i <= A.size(); i++) {
            for (int j = 1; j <= B.size(); j++) {
                dp[i][j] = A[i - 1] == B[j - 1] ? dp[i - 1][j - 1] + 1 : 0;
                res = max(res, dp[i][j]);
            }
        }
        return res;
    }
};

最後, 我明明就是為了練習二分搜尋才選這題, 這題要怎麼用binary search?

蠻難想到的, 他要用的二分搜尋是在找長度

長度多長就是我們要的答案, 由題目可知最長的長度會min(A.size(), B.size()) = l

所以我們就從這個 l 來開始二分找他的長度,

因為c++處理數組沒有像py那麼得輕鬆, 所以在這邊我們用字串替代

一樣我們先在設下兩個pointer left(0), right(l)

mid = (left + right) / 2

mid就是當前的長度, 我們只需要去驗證這個長度是不是真的做得到最大重複子字串, 做得到的話我們就試著把長度加長(left = mid+ 1), 做不到就減短, 直到right= =left為止

這邊我覺得能想到這做法已經很難了, 更麻煩的是數組轉成字串處理

class Solution {
  public:
    int findLength(vector<int> &A, vector<int> &B) {
        string strA = stringify(A);
        string strB = stringify(B);
        int left = 0;
        int right = min(A.size(), B.size());
        while (left <= right) {
            int mid = (left + right) / 2;
            if (helper(strA, strB, mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
    bool helper(string &strA, string &strB, int len) {
        std::unordered_set<string> st;
        for (int i = 0, j = len; j <= strA.size(); i++, j++) {
            st.insert(strA.substr(i, len));
        }
        for (int i = 0, j = len; j <= strB.size(); i++, j++) {
            if (st.count(strB.substr(i, len)))
                return true;
        }
        return false;
    }
    string stringify(vector<int> &nums) {
        string res;
        for (int num : nums)
            res += num;
        return res;
    }
};