Created by potrace 1.14, written by Peter Selinger 2001-2017 Zorch's Blog

字符串与回文系列题目总结

 
Category： DSA
  • zorchp
  • 2023年 04月08日

KMP算法

目的: 字符串匹配

思想: 当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

基本问题

28. 找出字符串中第一个匹配项的下标;

class Solution {
public:
    void getNext(int* nxt, const string& s) {
        int j{-1}; // j有两重含义, 前缀终止位置, 以及i之前最长相等前后缀长度
        nxt[0] = j;
        for (int i{1}; i < s.size(); ++i) {
            // 前后缀不同: 一直回退, j>=0保证回退索引正常
            while (j >= 0 && s[i] != s[j + 1]) j = nxt[j];
            // 因为这里, 相等情况下, j是从左往右递增更新的,
            // 所以保存了最长相等前后缀长度
            if (s[i] == s[j + 1]) ++j; // 找到了相同的前后缀
            nxt[i] = j;                // 更新数组
        }
    }
    int strStr(string s, string t) {
        int j{-1}, k = t.size();
        int nxt[k];
        getNext(nxt, t);
        for (int i{}; i < s.size(); ++i) {
            while (j >= 0 && s[i] != t[j + 1]) j = nxt[j];
            if (s[i] == t[j + 1]) ++j;
            if (j == k - 1) return i - j;
        }
        return -1;
    }
};

class Solution {
public:
    void getNext(int* nxt, const string& s) {
        int j{}; // j有两重含义, 前缀终止位置, 以及i之前最长相等前后缀长度
        nxt[0] = j;
        for (int i{1}; i < s.size(); ++i) {
            // 前后缀不同: 一直回退, j>=0保证回退索引正常
            while (j > 0 && s[i] != s[j]) j = nxt[j - 1];
            // 因为这里, 相等情况下, j是从左往右递增更新的,
            // 所以保存了最长相等前后缀长度
            if (s[i] == s[j]) ++j; // 找到了相同的前后缀
            nxt[i] = j;            // 更新数组
        }
    }
    int strStr(string s, string t) {
        int j{}, k = t.size();
        int nxt[k];
        getNext(nxt, t);
        for (int i{}; i < s.size(); ++i) {
            while (j > 0 && s[i] != t[j]) j = nxt[j - 1];
            if (s[i] == t[j]) ++j;
            if (j == k) return i - j + 1;
        }
        return -1;
    }
};

重复子串

459. 重复的子字符串;

KMP 的一个变形, 需要考虑 s+s 的匹配.

最小的回文子串

214. 最短回文串;

动态规划解法

  1. 647. 回文子串;

  2. 5. 最长回文子串;

  3. 516. 最长回文子序列;

    class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        int dp[n][n]; // dp[i][j]表示从i到j的最长回文子序列长度
        memset(dp, 0, sizeof(dp));
        for (int i{}; i < n; ++i) dp[i][i] = 1;
        for (int i{n - 1}; i >= 0; --i)
            for (int j{i + 1}; j < n; ++j)
                if (s[i] == s[j])
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                else
                    dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
        return dp[0][n - 1];
    }
};

  4. 132. 分割回文串 II;

双指针解法(中心扩展)

  1. 2108. 找出数组中的第一个回文字符串;(开胃菜)

    class Solution {
public:
    string firstPalindrome(vector<string>& words) {
        auto isPalindrome = [](const string& s) {
            int l{}, r = s.size() - 1;
            for (; l < r; ++l, --r) 
                if (s[l] != s[r]) return false;
            return true;
        };
        for (auto& s : words)
            if (isPalindrome(s))
                return s;
        return ""s;
    }
};

  2. 1616. 分割两个字符串得到回文串;

  3. 1638. 统计只差一个字符的子串数目;

    class Solution {
public:
    int countSubstrings(string s, string t) {
        int ans{}, m = s.size(), n = t.size();
        for (int i{}; i < m; ++i)
            for (int j{}; j < n; ++j) {
                if (s[i] != t[j]) {
                    int l{}, r{};
                    while (l < i && l < j && s[i - l - 1] == t[j - l - 1]) ++l;
                    while (i + r + 1 < m && j + r + 1 < n &&
                           s[i + r + 1] == t[j + r + 1])
                        ++r;
                    ans += (l + 1) * (r + 1);
                }
            }
        return ans;
    }
};

  4. 647. 回文子串;

    class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size(), ans{};
        for (int i{}; i < n; ++i)
            for (int j{}; j < 2; ++j) { // 奇偶中心
                int l{i}, r{i + j};
                // 扩展中心
                while (l >= 0 && r < n && s[l--] == s[r++]) ++ans;
            }
        return ans;
    }
};

  5. 5. 最长回文子串;(上一题直接加一个判断即可)

    class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size(), ansL{}, maxLen{};
        for (int i{}; i < n; ++i)
            for (int j{}; j < 2; ++j) { // 奇偶中心
                int l{i}, r{i + j};
                // 扩展中心
                while (l >= 0 && r < n && s[l--] == s[r++])
                    if (r - l - 1 > maxLen) maxLen = r - l - 1, ansL = l + 1;
            }
        return s.substr(ansL, maxLen);
    }
};

  6. 392. 判断子序列 - 力扣（LeetCode）;双指针最快

    class Solution {
public:
    bool isSubsequence(string s, string t) {
        int m = s.size(), n = t.size(), i{}, j{};
        while (i < m && j < n) {
            if (s[i] == t[j]) ++i;
            ++j;
        }
        return i == m;
    }
};
// 
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int m = s.size(), n = t.size(), i{}, j{};
        while (i < m && j < n) {
            while (i < m && j < n && s[i] == t[j]) ++i, ++j;
            ++j;
        }
        return i == m;
    }
};

贪心类

  1. 1147. 段式回文;

回溯类

  1. 131. 分割回文串;

    class Solution {
public:
    vector<vector<string>> partition(string s) {
        auto isPalindorme = [&](int l, int r) {
            for (; l < r; ++l, --r)
                if (s[l] != s[r]) return false;
            return true;
        };
        int n = s.size();
        vector<vector<string>> ans{};
        vector<string> path{};
        function<void(int)> f = [&](int start) {
            if (start == n) {
                ans.emplace_back(path);
                return;
            }
            for (int i{start}; i < n; ++i) {
                if (!isPalindorme(start, i)) continue;
                path.emplace_back(s.substr(start, i - start + 1));
                f(i + 1);
                path.pop_back();
            }
        };
        f(0);
        return ans;
    }
};
search search_off backspace