一、字符串比较

  • 题目一：同构字符串
    判断两个字符串是否同构。同构的定义是，可以通过把一个字符串的某些相同的字符转换成另一些相同的字符，使得两个字符串相同，且两种不同的字符不能够被转换成同一种字符。

    解答：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
        bool isIsomorphic(string s, string t) {
            unordered_map<int, int> hashMap;
            unordered_map<int, int> hashMap2;
            int n = s.length();
            for (int i = 0; i < n; ++i) {
                if (hashMap[s[i]] != 0 || hashMap2[t[i]] != 0) continue;
                hashMap[s[i]] = t[i];
                hashMap2[t[i]] = s[i];
            }
            for (int i = 0; i < n; ++i)
                s[i] = hashMap[s[i]];
            return s == t;
        }
    };

    提示：完完全全的一一对应关系，所以既需要正向记录也需要反向记录。

  • 题目二：回文字串
    给定一个字符，求其有多少个回文子字符串。回文的定义是左右对称。

    解答：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
    public:
        int extendSubstrings(const string& s, int l, int r) {
            int count = 0, n = s.length();
            while (l >= 0 && r < n && s[l] == s[r]) {
                --l;
                ++r;
                ++count;
            }
            return count;
        }

        int countSubstrings(string s) {
            int count = 0;
            for (int i = 0; i < s.length(); ++i) {
                count += extendSubstrings(s, i, i);     
                count += extendSubstrings(s, i, i + 1);
            }
            return count;
        }
    };

    提示：学会使用这种从中间往两边遍历的写法(注意要区分奇偶回文串)，还有一个时间复杂度为O(n)的Manacher算法，因为比较难以理解，所以就不在此处展示了，如想研究请自行google。

  • 题目三：计数二进制子串
    给定一个0-1字符串，求有多少非空子字符串的0和1数量相同，且0和1必须连续出现(比如0011、1100，但是0101不算)。

    解答：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Solution {
    public:
        int countBinarySubstrings(string s) {
            int stack0 = 0, stack1 = 0;
            int count = 0;
            for (int i = 0; i < s.length(); ++i) {
                if (s[i] == '0') {
                    if (i != 0 && s[i - 1] == '1')
                        stack0 = 0;
                    ++stack0;
                    if (stack1 != 0) {
                        ++count;
                        --stack1;
                    }
                } else {
                    if (i != 0 && s[i - 1] == '0')
                        stack1 = 0;
                    ++stack1;
                    if (stack0 != 0) {
                        ++count;
                        --stack0;
                    }
                }
            }
            return count;
        }
    };

    提示：很容易想到使用栈结构来完成这道题，那剩下的也就只有简单的处理01连续的问题，只需要判断一下当前连续的0或者是1是否被截断了即可。

  • 题目四：移除无效的括号
    给定一个包括字母和左右括号的字符串，求最少要移除多少个括号才能使其合法。

    解答：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution {
    public:
        string minRemoveToMakeValid(string s) {
            vector<int> stack;
            int n = s.length();
            for (int i = 0; i < n; ++i) {
                if (s[i] == '(') {
                    stack.push_back(i);
                } else if (s[i] == ')') {
                    if (!stack.empty()) {
                        stack.pop_back();
                        continue;
                    }
                    s[i] = '0';
                }
            }
            for (int index : stack) s[index] = '0';
            string res = "";
            for (char c : s) {
                if (c != '0') res.push_back(c);
            }
            return res;
        }
    };

    提示：典型的栈结构题，可以参考匹配括号的那道题。这道题无非多的就是需要把多余出来的’(‘也给移除出去，用stack记录一下下标即可轻松实现。

二、字符串理解

  • 题目：基本计算器 II
    给定一个包含加减乘除整数运算的字符串，求其运算的整数值结果。如果除不尽则向0取整。

    解答：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    class Solution {
    public:
        int calculate(string s) {
            char op = '+';
            int num1 = 0, num2 = 0;
            int i = 0;
            while (i < s.length()) {
                if (s[i] == ' ') {
                    ++i;
                    continue;
                }
                if (s[i] >= '0' && s[i] <= '9') {
                    string temp;
                    while (s[i] >= '0' && s[i] <= '9')
                        temp.push_back(s[i++]);
                    switch (op) {
                    case '+':
                        num1 += num2;
                        num2 = stoi(temp);
                        break;
                    case '-':
                        num1 += num2;
                        num2 = -stoi(temp);
                        break;
                    case '*':
                        num2 *= stoi(temp);
                        break;
                    case '/':
                        num2 /= stoi(temp);
                        break;
                    default:
                        break;
                    }
                } else {
                    op = s[i++];
                }
            }
            return num1 + num2;
        }
    };

    提示：没有括号改变优先级，遍历即可，需要有点耐心，通过区分num1和num2且立马计算num2来达到乘除优先级的效果。

三、字符串匹配

  • 题目：找出字符串中第一个匹配项的下标
    判断一个字符串是不是另一个字符串的子字符串，并返回其位置。

    解答：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    class Solution {
    private:
        vector<int> makeLps(string pattern) {
            int n = pattern.size();
            vector<int> lps(n);
            int maxLen = 0, i = 1;
            while (i < n) {
                if (pattern[i] == pattern[maxLen]) {
                    ++maxLen;
                    lps[i++] = maxLen;
                } else {
                    if (maxLen > 0) maxLen = lps[maxLen - 1];
                    else lps[i++] = 0;
                }
            }
            return lps;
        }

    public:
        int strStr(string haystack, string needle) {
            if (needle.empty()) return 0;
            vector<int> lps = makeLps(needle);
            int i = 0, j = 0;
            int n = needle.size();
            while (i < haystack.size()) {
                if (haystack[i] == needle[j]) {
                    ++i;
                    ++j;
                } else {
                    if (j > 0) j = lps[j - 1];
                    else ++i;
                }
                if (j == n) return i - n;
            }
            return -1;
        }
    };

    提示：还没看懂，之后还需要掌握的KMP算法，不过c++也可以直接使用find()方法来完成。

四、练习

  • 题目一：最长回文串
    给定一个包含大写字母和小写字母的字符串s，返回通过这些字母构造成的最长的回文串的长度。

    解答：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution {
    public:
        int longestPalindrome(string s) {
            unordered_map<char, int> hashMap;
            for (char c : s) ++hashMap[c];
            int res = 0;
            bool hasOdd = false;
            for (auto &[c, count] : hashMap) {
                res += (count / 2) * 2; 
                if (count % 2 == 1) hasOdd = true;
            }
            if (hasOdd) ++res; 
            return res;
        }
    };

    提示：注意即使有奇数个也可以取偶数个。

  • 题目二：无重复字符的最长子串
    给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。

    解答：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            int start = 0, end = 0;
            unordered_set<char> hashSet;
            int maxRes = 0;
            while (end < s.length()) {
                if (hashSet.count(s[end]) != 0) {
                    maxRes = max(maxRes, end - start);
                    while (hashSet.count(s[end]) != 0) {
                        hashSet.erase(s[start++]);
                    }
                }
                hashSet.emplace(s[end++]);
            }
            return max(maxRes, end - start);
        }
    };

    提示：并不是很难，需要记录一下出现过的字母方便进行长度截断并且重新开始。