LeetCode 97 Interleaving String

    
        标签：
        
            回溯法
        
            LeetCode
        
    发布于：2022-03-27 12:34:24
    编辑于：2022-03-27 12:41:08
    浏览量：990

概述

https://leetcode.com/problems/interleaving-string

回溯法

TLE 了，99 / 106 test cases passed：

class Solution {
public:
    bool ans = false;
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        backtrack(s1, s2, s3, 0, 0, 0);
        return ans;
    }
    
    void backtrack(string& s1, string& s2, string& s3, int i, int j, int k) {
        if (ans) return;
        if (i == s1.size() && j == s2.size()) {
            ans = true;
        }
        if (i == s1.size()) {
            if(s2.substr(j) == s3.substr(k)) {
                ans = true;
            }
            return;
        }
        if (j == s2.size()) {
            if (s1.substr(i) == s3.substr(k)) {
                ans = true;
            }
            return;
        }
        if (s1[i] == s3[k]) {
            i ++;
            k ++;
            backtrack(s1, s2, s3, i, j, k);
            k --;
            i --;
        }
        if (s2[j] == s3[k]) {
            j ++;
            k ++;
            backtrack(s1, s2, s3, i, j, k);
            k --;
            j --;
        }
    }
};

回溯法 + cache

实际上可能存在重复的函数调用，加个 cache 后就 faster then 100% 了：

class Solution {
public:
    bool ans = false;
    vector<vector<int>> cache;
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        cache.resize(s1.size() + 1, vector<int>(s2.size() + 1, -1));
        backtrack(s1, s2, s3, 0, 0, 0);
        return ans;
    }
    
    void backtrack(string& s1, string& s2, string& s3, int i, int j, int k) {
        if (ans) return;
        if (cache[i][j] != -1) return;
        if (i == s1.size() && j == s2.size()) {
            ans = true;
        }
        if (i == s1.size()) {
            if(s2.substr(j) == s3.substr(k)) {
                ans = true;
            }
            cache[i][j] = ans;
            return;
        }
        if (j == s2.size()) {
            if (s1.substr(i) == s3.substr(k)) {
                ans = true;
            }
            cache[i][j] = ans;
            return;
        }
        if (s1[i] == s3[k]) {
            i ++;
            k ++;
            backtrack(s1, s2, s3, i, j, k);
            k --;
            i --;
        }
        if (s2[j] == s3[k]) {
            j ++;
            k ++;
            backtrack(s1, s2, s3, i, j, k);
            k --;
            j --;
        }
        cache[i][j] = ans;
    }
};

Links: leetcode-97-interleaving-string