392/524-判断子序列

LeetCode

发布日期: 2021-12-02

LeetCode 392. Is Subsequence

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

method 1: 双指针

i指向子串，j指向原串，相同的话i递增，不管怎样j都要递增，j肯定会走到末尾，保证循环可以结束，最后看i会不会走完整个子串

bool isSubsequence(string s, string t) {
    int i = 0, j = 0;
    while (i < s.size() && j < t.size()) {
        if (s[i] == t[j]) i++;
        j++;
    }
    return i == s.size();
}

method 2: 动态规划

dp[i][j]：下标从0到i-1的s是下标从0到j-1的t的子序列的长度

如果s[i-1]==t[j-1]，那么子序列的长度加1，也就是dp[i][j] = dp[i-1][j-1]+1；如果不同，则维持原来的子序列长度，也就是s增加了一位，但t没有增加，所以dp[i][j] = dp[i][j-1]

相当于删除了t串的不匹配字符

bool isSubsequence(string s, string t) {
    int m = s.size(), n = t.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i - 1] == t[j - 1]) 
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else 
                dp[i][j] = dp[i][j - 1];
        }
    }
    return dp[m][n] == m;
}

只跟上一行有关，用2行就够了

bool isSubsequence(string s, string t) {
    int m = s.size(), n = t.size();
    vector<vector<int>> dp(2, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i - 1] == t[j - 1]) dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1;
            else dp[i % 2][j] = dp[i % 2][j - 1];
        }
    }
    return dp[m % 2][n] == m;
}

LeetCode 524. Longest Word in Dictionary through Deleting

LeetCode

Given a string s and a string array dictionary, return the longest string in the dictionary that can be formed by deleting some of the given string characters. If there is more than one possible result, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:

Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"

method: 双指针判断子序列

剪枝：如果后面的单词长度比我短，或者跟我一样长，但字典序比我大，那就不用判断了，肯定不会是他了

判断子序列：两个指针分别指向两个字符串

相同的话，子串指针+1
不同的话，原串指针+1
最后判断子串指针是不是走到末尾

bool isSub(string s, string t) {
    int i = 0, j = 0;
    while (i < s.size() && j < t.size()) {
        if (s[i] == t[j]) i++;
        j++;
    }
    return i == s.size();
}
string findLongestWord(string s, vector<string>& dictionary) {
    string res = "";
    for (auto dict : dictionary) {
        int i = res.size();
        int j = dict.size();
        if (i > j || (i == j && res < dict)) continue;  // 剪枝
        if (isSub(dict, s)) res = dict;
    }
    return res;
}