LYL's Blog
0%

leetcode刷题系列之字符串

发表于 分类于
本文字数： 32k 阅读时长 ≈ 29 分钟

这篇文章是leetcode刷题系列的第3部分——字符串。这里把有代表性的题目发出来，共计21道。字符串的问题杂且难，这一块，面试时碰到字符串问题时只能随机应变，没有固定的套路。

leetcode刷题系列其它文章组织如下：

1. 数组

2. 链表

3. 字符串

4. 二叉树

5. 队列和栈

6. 动态规划

7. 数据结构设计

8. 刷题小知识点

880. Decoded String at Index

给定一个编码字符串S。请你找出解码字符串并将其写入磁带。解码时，从编码字符串中每次读取一个字符 ，并采取以下步骤：

  • 如果所读的字符是字母，则将该字母写在磁带上。
  • 如果所读的字符是数字（例如d），则整个当前磁带总共会被重复写d - 1次。
  • 现在，对于给定的编码字符串S和索引K，查找并返回解码字符串中的第K个字母。

Constraints:

  • 2 <= S.length <= 100
  • S will only contain lowercase letters and digits 2 through 9.
  • S starts with a letter.
  • 1 <= K <= 10^9
  • It’s guaranteed that K is less than or equal to the length of the decoded string.
  • The decoded string is guaranteed to have less than 2^63 letters.

Example 1:

1
2
3
4
5
Input: S = "leet2code3", K = 10
Output: "o"
Explanation: 
The decoded string is "leetleetcodeleetleetcodeleetleetcode".
The 10th letter in the string is "o".

Example 2:

1
2
3
4
Input: S = "ha22", K = 5
Output: "h"
Explanation: 
The decoded string is "hahahaha".  The 5th letter is "h".
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
// 一般来说, 当解码的字符串等于某个长度为 size 的单词重复一定次数
// 例如 apple(size = 5) 组合重复 6 次时
// 第 k == 24 个的结果与第 k % size == 4 个的结果相同
// 根据这个思路来求解问题
string decodeAtIndex(string s, int k) {
    int n = s.size();
    long sz = 0;
    // 先计算解码后的总字符串的长度
    for(int i = 0; i < n; i++) {
        if(isalpha(s[i])) {
            sz++;
        }
        else {
            sz *= s[i] - '0';
        }
    }
    // 从后向前做逆向搜索
    for(int i = n - 1; i >= 0; i--) {
        // 如果当前字符是字母, 那么它必然在解码后的最后位置
        if(isalpha(s[i])) {
            // 如果这时就是第 k 个字符的话, 直接返回答案
            if(k % sz == 0) {
                return string(1, s[i]);
            }
            // 解码字符串的长度减 1
            sz--;
        }
        // 如果当前字符是数字
        else {
            // 此字符之前的解码字符串的长度就可以计算出来
            sz /= s[i] - '0';
            k %= sz;
        }
    }
    return "";
}
87. Scramble String

使用下面描述的算法可以扰乱字符串s得到字符串t：

  1. 如果字符串的长度为1，算法停止

  2. 如果字符串的长度> 1，执行下述步骤：

    • 在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串s，则可以将其分成两个子字符串x和y，且满足s = x + y。
    • 随机决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，s可能是s = x + y或者s = y + x。
    • 在x和y这两个子字符串上继续从步骤1开始递归执行此算法。

    给你两个长度相等的字符串s1和s2，判断s2是否是s1的扰乱字符串。如果是，返回true；否则，返回false。

示例：

1
2
3
4
5
6
7
8
9
10
11
输入：s1 = "great", s2 = "rgeat"
输出：true
解释：s1 上可能发生的一种情形是：
"great" --> "gr/eat" 在一个随机下标处分割得到两个子字符串
"gr/eat" --> "gr/eat" 随机决定：「保持这两个子字符串的顺序不变」
"gr/eat" --> "g/r / e/at" 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割
"g/r / e/at" --> "r/g / e/at" 随机决定：第一组「交换两个子字符串」，第二组「保持这两个子字符串的顺序不变」
"r/g / e/at" --> "r/g / e/ a/t" 继续递归执行此算法，将 "at" 分割得到 "a/t"
"r/g / e/ a/t" --> "r/g / e/ a/t" 随机决定：「保持这两个子字符串的顺序不变」
算法终止，结果字符串和 s2 相同，都是 "rgeat"
这是一种能够扰乱 s1 得到 s2 的情形，可以认为 s2 是 s1 的扰乱字符串，返回 true
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
// 由于递归过程中会出现许多的重复参数
// 使用一个哈希集合来记忆化递归过程
// 由于函数参数是两个字符串, 可将它们拼接在一起做为 key
unordered_set<string> memo;
bool isScramble(string s1, string s2) {
    if(memo.count(s1 + s2)) {
        return false;
    }
    if(s1 == s2) {
        return true;
    }
    if(s1.size() == 1) {
        return false;
    }
    // 判断字符对应个数是否相等
    // 先排序再判断
    string s1Copy = s1, s2Copy = s2;
    sort(s1Copy.begin(), s1Copy.end());
    sort(s2Copy.begin(), s2Copy.end());
    if(s1Copy != s2Copy) {
        return false;
    }
    int sz = s1.size();
    // s1 = L(s1) + R(s1), s2 = L(s2) + R(s2)
    // 两种情况, 看 L(s1) 是否可以转化为 L(s2) 以及 R(s1) 是否可以转化为 R(s2)
    for(int i = 1; i < sz; i++) {
        if(isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i, sz - i), s2.substr(i, sz - i)))
            return true;
        if(isScramble(s1.substr(i, sz - i), s2.substr(0, sz - i)) && isScramble(s1.substr(0, i), s2.substr(sz - i, i)))
            return true;
    }
    // 记录结果
    memo.insert(s1 + s2);
    return false;
}
28. Implement strStr()

实现strStr()函数。给你两个字符串haystack和needle，请你在haystack字符串中找出needle字符串出现的第一个位置（下标从0开始）。如果不存在，则返回-1 。当needle是空字符串时，返回0。

Example 1:

1
2
Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

1
2
Input: haystack = "aaaaa", needle = "bba"
Output: -1

Example 3:

1
2
Input: haystack = "", needle = ""
Output: 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
// kmp 算法
int strStr(string haystack, string needle) {
    int n = haystack.size();
    int m = needle.size();
    if(m == 0) {
        return 0;
    }
    vector<vector<int>> dfa(m, vector<int>(128));
    buildStateTransition(needle, dfa);
    int j = 0;
    for(int i = 0; i < n; i++) {
        j = dfa[j][haystack[i]];
        if(j == m) {
            return i + 1 - m;
        }
    }
    return -1;
}

void buildStateTransition(string& needle, vector<vector<int>>& dfa) {
    // base case
    dfa[0][needle[0]] = 1;
    int x = 0;
    for(int i = 1; i < needle.size(); i++) {
        for(int c = 0; c < 128; c++) {
            dfa[i][c] = dfa[x][c];
        }
        dfa[i][needle[i]] = i + 1;
        x = dfa[x][needle[i]];
    }
}
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
// sunday 算法
int strStr(string haystack, string needle) {
    int n = haystack.size();
    int m = needle.size();
    if(m == 0) {
        return 0;
    }
    unordered_map<char, int> shift;
    for(int i = 0; i < m; i++) {
        shift[needle[i]] = m - i;
    }
    int pos_n = 0, pos_m = 0;
    while(pos_n <= n - m) {
        pos_m = 0;
        while(haystack[pos_n + pos_m] == needle[pos_m]) {
            pos_m++;
            if(pos_m == m) {
                return pos_n;
            }
        }
        if(shift.count(haystack[pos_n + m])) {
            pos_n += shift[haystack[pos_n + m]];
        }
        else {
            pos_n += m + 1;
        }
    }
    return -1;
}
187. Repeated DNA Sequences

所有DNA都由一系列缩写为'A'，'C'，'G'和'T'的核苷酸组成，例如："ACGAATTCCG"。在研究DNA时，识别DNA中的重复序列有时会对研究非常有帮助。

编写一个函数来找出所有目标子串，目标子串的长度为10，且在DNA字符串s中出现次数超过一次。

Example 1:

1
2
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

Example 2:

1
2
Input: s = "AAAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]

Constraints:

  • 1 <= s.length <= 105
  • s[i] is either 'A', 'C', 'G', or 'T'
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 滑动窗口切片 + 哈希集合 切片复杂度为 O(k)
// 总 O(k(n - k))
vector<string> findRepeatedDnaSequences(string s) {
    int size = s.size();
    if(size <= 10) {
        return vector<string>();
    }
    unordered_set<string> visited;
    unordered_set<string> output;
    int k = 10;
    string subStr;
    for(int i = 0; i <= size - k; i++) {
        subStr = s.substr(i, k);
        if(visited.count(subStr)) {
            output.insert(subStr);
        }
        visited.insert(subStr);
    }
    vector<string> res;
    for(auto str : output) {
        res.push_back(str);
    }
    return res;
}
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/*
Rabin-Karp 字符串编码介绍
由于我们需要频繁判断两个字串是否相同, 直接切片比较的话, 复杂度和子串的长度成正比
这样, 我们将字符串中的字符(全小写)映射到 0-25 的数字
给定窗口长度为 k 的字符串, 窗口内的字符序列可以表示成一个 base = 26 进制的数字序列
比如 将 k = 4 的字符串 c1c2c3c4 转换为数字串 a1a2a3a4, 它对应的十进制值为
key = a1*26^3 + a2*26^2 + a3*26^1 + a4*26
	= a1*base^(k-1) + a2*base^(k-2) + a3*base^(k-3) + a4*base
然后将 key 做哈希表的键, 这样我们比较 是否有相同的 key 就可以判断出是否有相同的串
为什么说这样快呢? 对于窗口 a1a2a3a4 -> a2a3a4a5
key = ((a1*base^(k-1) + a2*base^(k-2) + a3*base^(k-3) + a4*base) - a1*base^(k-1))*base + a5*base
	= (key - a1*base^(k-1))*base + a5*base
	= key*base - a1*base^k + a5*base
可以在 O(1) 时间算出新窗口的 key, 如果直接从字符串中切片的话需要 O(k) 时间
*/

// 滑动窗口切片 + Rabin-Karp 字符串编码使得切片复杂度为 O(1)
// 总 O(n - k)
vector<string> findRepeatedDnaSequences(string s)
{
    int size = s.size();
    if(size <= 10) {
        return vector<string>();
    }
    unordered_map<char, int> encode;
    int i = 0;
    // 将这四个字符分别映射为 0 1 2 3, 所以 base 为 4
    for(char c : {'A', 'C', 'G', 'T'}) {
        encode[c] = i++;
    }
    vector<int> nums(s.size());
    // 将原字符串中的字符装成数字序列
    for(i = 0; i < nums.size(); i++) {
        nums[i] = encode[s[i]];
    }
    int base = 4, k = 10;
    int baseK = pow(base, k);
    int key = 0;
    // 计算第一个窗口的 key
    for(i = 0; i < k; i++) {
        key = key * base + nums[i];
    }
    unordered_set<int> visited;
    unordered_set<string> output;
    // 将第一个窗口的 key 先放进去表示已经访问
    visited.insert(key);
    // 下面开始滑动窗口
    // i = 10;
    while(i < size) {
        // 计算新窗口的 key
        key = key * base - nums[i - k] * baseK + nums[i];
        // 如果已经存在, 表示有重复的串
        // 将串取出
        if(visited.count(key)) {
            output.insert(s.substr(i - k + 1, k));
        }
        // 新窗口也已访问
        visited.insert(key);
        i++;
    }
    vector<string> res;
    for(auto str : output) {
        res.push_back(str);
    }
    return res;
}
1044. Longest Duplicate Substring

给出一个字符串S，考虑其所有重复子串（S的连续子串，出现两次或多次，可能会有重叠）。

返回任何具有最长可能长度的重复子串。（如果S不含重复子串，那么答案为""。）

Example 1:

1
2
Input: s = "banana"
Output: "ana"

Example 2:

1
2
Input: s = "abcd"
Output: ""

Constraints:

  • 2 <= s.length <= 3 * 104
  • s consists of lowercase English letters.
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
41
42
43
44
45
46
47
48
49
50
51
// 滑动窗口切片 + Rabin-Karp 字符串编码使得切片复杂度为 O(1)
// 由于我们希望找到一个最长的重复串, 最长莫不过 s.size()
// 所以我们每次固定窗口的大小为 k, k 范围时[0, s.size())
// 在这个区间可以使用 二分搜索 提高效率
string longestDupSubstring(string s)
{
    unordered_map<char, int> digit;
    for(char c = 'a'; c <= 'z'; c++)
        digit[c] = c - 'a';
    string res;
    // 外循环二分搜索, 内循环滑动窗口
    int minK = 0;
    int maxK = (int)s.size();
    while(minK < maxK)
    {
        string subStr;
        unordered_set<long> visited;
        int k = minK + (maxK - minK >> 1); // 窗口大小
        
        /* Rabin-Karp 编码算法 */
        int base = 26;
        long baseK = pow(base, k);
        long key = 0;
        // 计算第一个窗口的 key
        int i = 0;
        for(; i < k; i++)
            key = key * base + digit[s[i]];
        visited.insert(key);
        while(i < s.size())
        {
            key = key * base - (digit[s[i - k]] * baseK) + digit[s[i]];
            if(visited.count(key))
            {
                subStr = s.substr(i - k + 1, k);
                break;
            }
            visited.insert(key);
            i++;
        }
        /* Rabin-Karp 编码算法 */
        
        if(!subStr.empty())
        {
            minK = k + 1;
            res = subStr;
        }
        else
            maxK = k;
    }
    return res;
}
316. Remove Duplicate Letters

给你一个字符串s，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

Example 1:

1
2
Input: s = "bcabc"
Output: "abc"

Example 2:

1
2
Input: s = "cbacdcbc"
Output: "acdb"

Constraints:

  • 1 <= s.length <= 104
  • s consists of lowercase English letters.
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
// 类似单调栈的技巧
string removeDuplicateLetters(string s)
{
    unordered_map<char, int> counter;
    for(char c : s) counter[c]++;
    // 记录已经在栈中的字符, 栈中的字符唯一
    unordered_set<char> existed;
    // 把字符串当栈使用
    string res;
    // 顺序访问字符
    for(char c : s)
    {
        // 每访问一个字符, 相应数量减一
        counter[c]--;
        // 如果该字符已经在栈中了, 直接删除即可
        if(existed.count(c)) continue;
        // 否则, 如果字典序比栈顶元素小并且在后边还有栈顶的字符, 删除栈顶字符
        // 因为反正后面还会遇到的嘛
        while(!res.empty() && res.back() > c && counter[res.back()] > 0)
        {
            existed.erase(res.back());
            res.pop_back();
        }
        // 将当前字符入栈
        res.push_back(c);
        existed.insert(c);
    }
    
    return res;
}
1839. Longest Substring Of All Vowels in Order

当一个字符串满足如下条件时，我们称它是美丽的 ：

所有5个英文元音字母（'a'，'e'，'i'，'o'，'u'）都必须至少出现一次。
这些元音字母的顺序都必须按照字典序升序排布（也就是说所有的'a'都在'e'前面，所有的'e'都在'i'前面，以此类推）
比方说，字符串"aeiou"和"aaaaaaeiiiioou"都是美丽的，但是"uaeio" ，"aeoiu"和"aaaeeeooo"不是美丽的。

给你一个只包含英文元音字母的字符串word，请你返回word中最长美丽子字符串的长度。如果不存在这样的子字符串，请返回0。

子字符串是字符串中一个连续的字符序列。

示例 1：

1
2
3
输入：word = "aeiaaioaaaaeiiiiouuuooaauuaeiu"
输出：13
解释：最长子字符串是 "aaaaeiiiiouuu", 长度为 13

示例 2：

1
2
3
输入：word = "aeeeiiiioooauuuaeiou"
输出：5
解释：最长子字符串是 "aeiou", 长度为 5

提示：

  • 1 <= word.length <= 5 * 10^5
  • word只包含字符'a'，'e'，'i'，'o' 和'u'。
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
int longestBeautifulSubstring(string word)
{
    unordered_set<char> setting;
    unordered_map<char, unordered_set<char>> mapping;
    mapping['a'].insert({'a', 'e'});
    mapping['e'].insert({'e', 'i'});
    mapping['i'].insert({'i', 'o'});
    mapping['o'].insert({'o', 'u'});
    mapping['u'].insert('u');
    int res = 0;
    int left = 0, right = 0;
    while(right < word.size())
    {
        char a = word[right];
        if(right > left && !mapping[word[right - 1]].count(a))
        {
            window.clear();
            left = right;
            continue;
        }
        right++;
        setting.insert(a);

        if(setting.size() == 5)
            res = max(res, right - left);
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int longestBeautifulSubstring(string word)
{
    int res = 0, types = 1, len = 1;
    for(int i = 1; i < word.length(); i++)
    {
        // 更新当前字符串长度
        if(word[i] >= word[i - 1]) len++;
        // 更新当前字符种类
        if(word[i] > word[i - 1]) types++;
        // 当前字符串不美丽，从当前字符重新开始
        if(word[i] < word[i - 1])
        {
            types = 1;
            len = 1;
        }
        // 更新最大字符串
        if(types == 5) res = max(res, len);
    } 
    return res;
}
5. Longest Palindromic Substring

给你一个字符串s，找到s中最长的回文子串。

Example 1:

1
2
3
Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1
2
Input: s = "cbbd"
Output: "bb"
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
// 中心开花, 时间复杂度为 O(n2), 空间复杂度为 O(1)
string longestPalindrome(string s) {
    int n = s.size();
    auto palindrome = [&](int left, int right) {
        while(left >= 0 && right < n && s[left] == s[right]) {
            left--;
            right++;
        }
        return make_pair(left + 1, right - left - 1);
    };
    int start = 0, len = 0;
    for(int i = 0; i < n; i++) {
        auto [start1, len1] = palindrome(i, i);
        auto [start2, len2] = palindrome(i, i + 1);
        if(len < len1) {
            start = start1;
            len = len1;
        }
        if(len < len2) {
            start = start2;
            len = len2;
        }
    }
    return s.substr(start, len);
}
76. Minimum Window Substring

给你一个字符串s和一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串""。

注意：如果s中存在这样的子串，我们保证它是唯一的答案。

Example 1:

1
2
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Example 2:

1
2
Input: s = "a", t = "a"
Output: "a"
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
string minWindow(string s, string t) {
    unordered_map<char, int> window, need;
    for(char c : t) {
        need[c]++;
    }
    int left = 0, right = 0;
    size_t valid = 0;
    int start = 0, len = 0;
    while(right < s.size()) {
        char a = s[right++];
        if(need.count(a)) {
            window[a]++;
            if(window[a] == need[a]) {
                valid++;
            }
        }
        while(valid == need.size()) {
            if(len == 0 || right - left < len) {
                start = left;
                len = right - left;
            }
            char d = s[left++];
            if(need.count(d)) {
                if(window[d] == need[d]) {
                    valid--;
                }
                window[d]--;
            }
        }
    }
    return s.substr(start, len);
}
567. Permutation in String

给定两个字符串s1和s2，写一个函数来判断s2是否包含s1的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

Example 1:

1
2
3
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

1
2
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
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
bool checkInclusion(string s1, string s2) {
    unordered_map<char, int> window, need;
    for(char c : s1) {
        need[c]++;
    }
    int left = 0, right = 0, n = s2.size(), m = s1.size();
    size_t valid = 0;
    while(right < n) {
        char a = s2[right++];
        if(need.count(a)) {
            window[a]++;
            if(window[a] == need[a]) {
                valid++;
            }
        }
        while(valid == need.size()) {
            if(right - left == m) {
                return true;
            }
            char d = s2[left++];
            if(need.count(d)) {
                if(window[d] == need[d]) {
                    valid--;
                }
                window[d]--;
            }
        }
    }
    return false;
}
3. Longest Substring Without Repeating Characters

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

Example 1:

1
2
3
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

1
2
Input: s = ""
Output: 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> window;
    int left = 0, right = 0, res = 0;
    while(right < s.size()) {
        char a = s[right++];
        window[a]++;
        while(window[a] > 1) {
            char d = s[left++];
            window[d]--;
        }
        res = max(res, right - left);
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
int lengthOfLongestSubstring(string s) {
    vector<bool> visited(128);
    int lo = 0, hi = 0, len = 0;
    int n = s.size();
    while(hi < n) {
        while(visited[s[hi]]) {
            visited[s[lo++]] = false;
        }
        visited[s[hi++]] = true;
        len = max(len, hi - lo);
    }
    return len;
}
438. Find All Anagrams in a String

给定一个字符串s和一个非空字符串p，找到s中所有是p的字母异位词的子串，返回这些子串的起始索引。字符串只包含小写英文字母，并且字符串s和p的长度都不超过20100。

说明：

  • 字母异位词指字母相同，但排列不同的字符串。
  • 不考虑答案输出的顺序。

Example 1:

1
2
3
4
5
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

1
2
3
4
5
6
Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
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
vector<int> findAnagrams(string s, string p) {
    vector<int> window(26), need(26);
    for(char c : p) {
        need[c - 'a']++;
    }
    // 表示窗口内字符种类和所需要的字符种类数目的差距
    int diff = 0;
    for(int cnt : need) {
        if(cnt > 0) {
            diff++;
        }
    }
    vector<int> res;
    int n = s.size(), m = p.size();
    int left = 0, right = 0;
    while(right < n) {
        char a = s[right++] - 'a';
        if(need[a] > 0) {
            window[a]++;
            if(window[a] == need[a]) {
                diff--;
            }
        }
        // 对每个窗口内数据都判断一下
        if(right - left == m) {
            if(diff == 0) {
                res.push_back(left);
            }
            char d = s[left++] - 'a';
            if(need[d] > 0) {
                if(window[d] == need[d]) {
                    diff++;
                }
                window[d]--;
        	}
        }
    }
    return res;
}
395. Longest Substring with At Least K Repeating Characters

给你一个字符串s和一个整数k，请你找出s中的最长子串， 要求该子串中的每一字符出现次数都不少于k。返回这一子串的长度。

Example 1:

1
2
3
Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

1
2
3
Input: s = "ababbc", k = 2
Output: 5
Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
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
// 这题有一个点很关键
// 有一些字符的出现次数小于 k
// 如果窗口内包含这些字符的话, 肯定是不符合要求的
// 常规的滑动窗口思路需要做些改动
int longestSubstring(string s, int k) {
    int n = s.size();
    // 总字符数量小于 k 肯定不符合条件
    if(n < k) {
        return 0;
    }
    unordered_map<char, int> char2cnt;
    for(char c : s) {
        char2cnt[c]++;
    }
    unordered_set<int> uniqueString(s.begin(), s.end());
    vector<string> afterSplit;
    auto split = [&](const char sep) {
        // 清空数组
        vector<string>().swap(afterSplit);
        istringstream iss(s);
        string str;
        while(getline(iss, str, sep)) {
            afterSplit.emplace_back(str);
        }
    };
    for(char c : uniqueString) {
        if(char2cnt[c] < k) {
            split(c);
            int len = 0;
            for(auto&& str : afterSplit) {
                len = max(len, longestSubstring(str, k));
            }
            return len;
        }
    }
    return s.size();
}
402. Remove K Digits

给定一个以字符串表示的非负整数num，移除这个数中的k位数字，使得剩下的数字最小。

注意：

  • num的长度小于10002且≥ k。
  • num不会包含任何前导零。

Example 1:

1
2
3
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

1
2
3
Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

1
2
3
Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 贪心思想 + 单调栈
string removeKdigits(string num, int k) {
    int n = num.size();
    if(n <= k) {
        return "0";
    }
    int remain = n - k;
    string s;
    for(char c : num) {
        while(k > 0 && !s.empty() && s.back() > c) {
            s.pop_back();
            k--;
        }
        s += c;
    }
    s = s.substr(0, remain);
    /删除前导零
    int i = 0;
    while(i < remain && s[i] == '0') {
        i++;
    }
    return i == remain ? "0" : s.substr(i);
}
321. Create Maximum Number

给定长度分别为m和n的两个数组，其元素由0-9构成，表示两个自然数各位上的数字。现在从这两个数组中选出k (k <= m + n)个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为k的数组。

说明：请尽可能地优化你算法的时间和空间复杂度。

Example 1:

1
2
Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
Output: [9,8,6,5,3]

Example 2:

1
2
Input: nums1 = [6,7], nums2 = [6,0,4], k = 5
Output: [6,7,6,0,4]

Example 3:

1
2
Input: nums1 = [3,9], nums2 = [8,9], k = 3
Output: [9,8,9]
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// 这题是上一题 402 的超级进阶
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
    int m = nums1.size(), n = nums2.size();
    vector<int> res;
    for(int i = 0; i <= k; i++) {
        if(i <= m && k - i <= n) {
            res = max(res, merge(maxNumber(nums1, i), maxNumber(nums2, k - i)));
        }
    }
    return res;
}
// 从 nums 中取出能够拼接得到最大的 k 个数
vector<int> maxNumber(vector<int>& nums, int k) {
    vector<int> s;
    int del = nums.size() - k;
    for(int num : nums) {
        while(del > 0 && !s.empty() && s.back() < num) {
            s.pop_back();
            del--;
        }
        s.push_back(num);
    }
    while(s.size() > k) {
        s.pop_back();
    }
    return s;
}
// 合并两个数组, 其中比较大小的规则比较特殊
vector<int> merge(vector<int> nums1, vector<int> nums2) {
    int m = nums1.size(), n = nums2.size();
    vector<int> merged(m + n);
    int i = 0, j = 0, k = 0;
    while(i < m && j < n) {
        if(compare(nums1, i, nums2, j)) {
            merged[k++] = nums1[i++];
        }
        else {
            merged[k++] = nums2[j++];
        }
    }
    while(i < m) {
        merged[k++] = nums1[i++];
    }
    while(j < n) {
        merged[k++] = nums2[j++];
    }
    return merged;
}
// 合并数组时特殊的比较规则, 主要是处理两个数相等的情况, 这时要看后面数字的大小
bool compare(vector<int>& nums1, int i, vector<int>& nums2, int j) {
    if(i >= nums1.size()) {
        return false;
    }
    if(j >= nums2.size()) {
        return true;
    }
    if(nums1[i] > nums2[j]) {
        return true;
    }
    if(nums1[i] < nums2[j]) {
        return false;
    }
    return compare(nums1, i + 1, nums2, j + 1);
}
1754. Largest Merge Of Two Strings

给你两个字符串word1和word2。你需要按下述方式构造一个新字符串merge：如果word1或word2非空，选择下面选项之一继续操作：

  • 如果word1非空，将word1中的第一个字符附加到merge的末尾，并将其从word1中移除。
    例如，word1 = "abc"且merge = "dv"，在执行此选项操作之后，word1 = "bc"，同时merge = "dva"。

  • 如果word2非空，将word2中的第一个字符附加到merge的末尾，并将其从word2中移除。
    例如，word2 = "abc"且merge = ""，在执行此选项操作之后，word2 = "bc"，同时merge = "a"。

    返回你可以构造的字典序最大的合并字符串merge。

Example 1:

1
2
3
4
5
6
7
8
9
Input: word1 = "cabaa", word2 = "bcaaa"
Output: "cbcabaaaaa"
Explanation: One way to get the lexicographically largest merge is:
- Take from word1: merge = "c", word1 = "abaa", word2 = "bcaaa"
- Take from word2: merge = "cb", word1 = "abaa", word2 = "caaa"
- Take from word2: merge = "cbc", word1 = "abaa", word2 = "aaa"
- Take from word1: merge = "cbca", word1 = "baa", word2 = "aaa"
- Take from word1: merge = "cbcab", word1 = "aa", word2 = "aaa"
- Append the remaining 5 a's from word1 and word2 at the end of merge.

Example 2:

1
2
Input: word1 = "abcabc", word2 = "abdcaba"
Output: "abdcabcabcaba"

Constraints:

  • 1 <= word1.length, word2.length <= 3000
  • word1 and word2 consist only of lowercase English letters.
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
// 这题就是用到上一题 321 的合并思路
string largestMerge(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    string merged(m + n);
    int i = 0, j = 0, k = 0;
    while(i < m && j < n) {
        if(compare(word1, i, word2, j)) {
            merged[k++] = word1[i++];
        }
        else {
            merged[k++] = word2[j++];
        }
    }
    while(i < m) {
        merged[k++] = word1[i++];
    }
    while(j < n) {
        merged[k++] = word2[j++];
    }
    return merged;
}

bool compare(string& word1, int i, string& word2, int j) {
    if(i >= word1.size()) {
        return false;
    }
    if(j >= word2.size()) {
        return true;
    }
    if(word1[i] < word2[j]) {
        return false;
    }
    if(word1[i] > word2[j]) {
        return true;
    }
    return compare(word1, i + 1, word2, j + 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 因为这题是处理字符串, 比较函数可以不用单独写
// 但是效率会降低很多
string largestMerge(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    string merged;
    int i = 0, j = 0, k = 0;
    while(i < m && j < n) {
        if(word1.substr(i) > word2.substr(j)) {
            merged += word1[i++];
        }
        else {
            merged += word2[j++];
        }
    }
    // 直接切片就行了
    if(i < m) {
        merged += word1.substr(i);
    }
    if(j < n) {
        merged += word2.substr(j);
    }
    return merged;
}
8. 字符串转换整数 (atoi)

请你来实现一个myAtoi(string s)函数，使其能将字符串转换成一个32位有符号整数（类似C/C++中的atoi函数）。

函数myAtoi(string s)的算法如下：

  • 读入字符串并丢弃无用的前导空格

  • 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。

  • 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。

  • 将前面步骤读入的这些数字转换为整数（即，"123"-> 123，"0032" -> 32）。如果没有读入数字，则整数为0。必要时更改符号（从步骤2开始）。

  • 如果整数数超过32位有符号整数范围[−2^31, 2^31 − 1]，需要截断这个整数，使其保持在这个范围内。具体来说，小于−2^31的整数应该被固定为−2^31，大于2^31−1的整数应该被固定为2^31−1 。

  • 返回整数作为最终结果。

    注意：

  • 本题中的空白字符只包括空格字符' '。

  • 除前导空格或数字后的其余字符串外，请勿忽略任何其他字符。

题解：尽量不使用库函数、一次遍历（Java） - 字符串转换整数 (atoi) - 力扣（LeetCode）

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："42"（读入 "42"）
           ^
解析得到整数 42
由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42

示例 2：

1
2
3
4
5
6
7
8
9
10
11
输入：s = "   -42"
输出：-42
解释：
第 1 步："   -42"（读入前导空格，但忽视掉）
            ^
第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
             ^
第 3 步："   -42"（读入 "42"）
               ^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42

示例 3：

1
2
3
4
5
6
7
8
9
10
11
输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
             ^
解析得到整数 4193
由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193

示例 4：

1
2
3
4
5
6
7
8
9
10
11
输入：s = "words and 987"
输出：0
解释：
第 1 步："words and 987"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："words and 987"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："words and 987"（由于当前字符 'w' 不是一个数字，所以读入停止）
         ^
解析得到整数 0，因为没有读入任何数字。
由于 0 在范围 [-231, 231 - 1] 内，最终结果为 0

示例 5：

1
2
3
4
5
6
7
8
9
10
11
输入：s = "-91283472332"
输出：-2147483648
解释：
第 1 步："-91283472332"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："-91283472332"（读入 '-' 字符，所以结果应该是负数）
          ^
第 3 步："-91283472332"（读入 "91283472332"）
                     ^
解析得到整数 -91283472332
由于 -91283472332 小于范围 [-231, 231 - 1] 的下界，最终结果被截断为 -2^31 = -2147483648
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
41
42
43
44
45
46
47
48
// 根据示例 1, 需要去掉前导空格
// 根据示例 2, 需要判断第 1 个字符为 + 和 - 的情况
// 因此, 可以设计一个变量 sign, 初始化的时候为 1, 如果遇到 -, 将 sign 修正为 -1
// 判断是否是数字, 可以使用字符的 ASCII 码数值进行比较, 即 0 <= c <= '9'
// 根据示例 3 和示例 4, 在遇到第 1 个不是数字的字符的情况下, 转换停止, 退出循环
// 根据示例 5, 如果转换以后的数字超过了 int 类型的范围, 需要截取
// 这里不能将结果 res 变量设计为 long 类型
// 注意: 由于输入的字符串转换以后也有可能超过 long 类型
// 因此需要在循环内部就判断是否越界, 只要越界就退出循环, 这样也可以减少不必要的计算
// 由于涉及下标访问, 因此全程需要考虑数组下标是否越界的情况
int myAtoi(string str) {
    int n = str.size();
    int idx = 0;
    // 去除前导空格
    while(idx < n && str[idx] == ' ') {
        idx++;
    }
    if(idx == n) {
        return 0;
    }
    int sign = 1;
    // 处理第 1 个非空字符为正负符号, 这两个判断需要写在一起
    if(str[idx] == '+') {
        idx++;
    }
    else if(str[idx] == '-') {
        sign = -1;
        idx++;
    }
    int number = 0;
    while(idx < n) {
        char c = str[idx];
        if(c < '0' || c > '9') {
            break;
        }
        int num = c - '0';
        // 溢出处理
        if(number > INT_MAX / 10 || (number == INT_MAX / 10 && num > INT_MAX % 10)) {
            return INT_MAX;
        }
        if(number < INT_MIN / 10 || (number == INT_MIN / 10 && num > -(INT_MIN % 10))) {
            return INT_MIN;
        }
        number = number * 10 + sign * num;
        idx++;
    }
    return number;
}
43. Multiply Strings

给定两个以字符串形式表示的非负整数num1和num2，返回num1和num2的乘积，它们的乘积也表示为字符串形式。

参考题解：优化版竖式(打败99.4%) - 字符串相乘 - 力扣（LeetCode）

示例 1:

1
2
输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

1
2
输入: num1 = "123", num2 = "456"
输出: "56088"
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 模拟普通竖式乘法
// 将每一步的乘法结果相加即可
string multiply(string num1, string num2) {
    if(num1 == "0" || num2 == "0") {
        return "0";
    }
    string res;
    int m = num1.size();
    int n = num2.size();
    int times = 0;
    for(int i = m - 1; i >= 0; i--) {
        string num;
        int carry = 0;
        for(int j = n - 1; j >= 0; j--) {
            int temp = (num1[i] - '0') * (num2[j] - '0') + carry;
            carry = temp / 10;
            num += to_string(temp % 10);
        }
        if(carry != 0) {
            num += to_string(carry);
        }
        reverse(num.begin(), num.end());
        for(int k = 0; k < times; k++) {
            num += '0';
        }
        times++;
        res = stringPlus(res, num);
    }
    return res;
}
// 字符串数字相加
string stringPlus(const string& num1, const string& num2) {
    int m = num1.size();
    if(m == 0) {
        return num2;
    }
    int n = num2.size();
    if(n == 0) {
        return num1;
    }
    string res;
    int i = m - 1, j = n - 1;
    int carry = 0;
    while(i >= 0 || j >= 0 || carry > 0) {
        // 这里的一个技巧就是短的字符串前面以 0 补齐
        int x = i < 0 ? 0 : num1[i] - '0';
        int y = j < 0 ? 0 : num2[j] - '0';
        int temp = x + y + carry;
        res += to_string(temp % 10);
        carry = temp / 10;
        i--;
        j--;
    }
    reverse(res.begin(), res.end());
    return res;
}
93. 复原 IP 地址

给定一个只包含数字的字符串，用以表示一个IP地址，返回所有可能从s获得的有效IP地址 。你可以按任何顺序返回答案。

有效IP地址 正好由四个整数（每个整数位于0到255之间组成，且不能含有前导0），整数之间用'.'分隔。

例如：”0.1.2.201”和”192.168.1.1”是有效IP地址，但是”0.011.255.245”、”192.168.1.312”和”192.168@1.1“是无效IP地址。

示例 1：

1
2
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

1
2
输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

1
2
输入：s = "010010"
输出：["0.10.0.10","0.100.1.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
// 回溯
vector<string> restoreIpAddresses(string s) {
    vector<string> res;
    auto dfs = [&](auto&& dfs, int cnt, int idx, string&& str) {
        if(cnt >= 4) {
            if(idx == s.size()) {
                // 需要将最前面的 '.' 删掉
                res.emplace_back(str.substr(1));
            }
            return;
        }
        // 重要的剪枝, 前导符为 0 时, 这一段只能为 0
        if(s[idx] == '0') {
            dfs(dfs, cnt + 1, idx + 1, str + ".0");
            return;
        }
        string temp;
        for(int i = idx; i < s.size(); i++) {
            temp += s[i];
            if(stoi(temp) <= 255) {
                dfs(dfs, cnt + 1, i + 1, str + "." + temp);
            }
            else {
                break;
            }
        }
    };
    dfs(dfs, 0, 0, "");
    return res;
}
468. 验证IP地址

编写一个函数来验证输入的字符串是否是有效的IPv4或IPv6地址。

  • 如果是有效的IPv4地址，返回"IPv4"；

  • 如果是有效的IPv6地址，返回"IPv6"；

  • 如果不是上述类型的IP地址，返回"Neither"。

    IPv4地址由十进制数和点来表示，每个地址包含4个十进制数，其范围为0 - 255， 用(".")分割。比如，172.16.254.1；同时，IPv4地址内的数不会以0开头。比如，地址172.16.254.01是不合法的。

    IPv6地址由8组16进制的数字来表示，每组表示16比特。这些组数字通过(":")分割。比如， 2001:0db8:85a3:0000:0000:8a2e:0370:7334是一个有效的地址。而且，我们可以加入一些以0开头的数字，字母可以使用大写，也可以是小写。所以，2001:db8:85a3:0:0:8A2E:0370:7334也是一个有效的IPv6 address地址 (即，忽略0开头，忽略大小写）。

    然而，我们不能因为某个组的值为0，而使用一个空的组，以至于出现(::)的情况。 比如，2001:0db8:85a3::8A2E:0370:7334是无效的IPv6地址。

    同时，在IPv6地址中，多余的0也是不被允许的。比如，02001:0db8:85a3:0000:0000:8a2e:0370:7334是无效的。

示例 1：

1
2
3
输入：IP = "172.16.254.1"
输出："IPv4"
解释：有效的 IPv4 地址，返回 "IPv4"

示例 2：

1
2
3
输入：IP = "2001:0db8:85a3:0:0:8A2E:0370:7334"
输出："IPv6"
解释：有效的 IPv6 地址，返回 "IPv6"

示例 3：

1
2
3
输入：IP = "256.256.256.256"
输出："Neither"
解释：既不是 IPv4 地址，又不是 IPv6 地址

示例 4：

1
2
输入：IP = "2001:0db8:85a3:0:0:8A2E:0370:7334:"
输出："Neither"

示例 5：

1
2
输入：IP = "1e1.4.5.6"
输出："Neither"

提示：

  • IP仅由英文字母，数字，字符'.'和':'组成。
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Solution {
public:
    string validIPAddress(string IP) {
        if(validIPv4Address(IP)) {
            return "IPv4";
        }
        if(validIPv6Address(IP)) {
            return "IPv6";
        }
        return "Neither";
    }

    bool validIPv4Address(const string& IPv4) {
        vector<string> ip;
        split(IPv4, ip, '.');
        if(ip.size() != 4) {
            return false;
        }
        for(auto&& elem : ip) {
            if(elem.empty() || elem.size() > 3) {
                return false;
            }
            // 处理前导符为 0 的情况
            if(elem.size() > 1 && elem[0] == '0') {
                return false;
            }
            // 处理非法字符的情况，如 1e1等
            for(char c : elem) {
                if(c < '0' || c > '9') {
                    return false;
                }
            }
            if(stoi(elem) > 255) {
                return false;
            }
        }
        return true;
    }

    bool validIPv6Address(const string& IPv6) {
        vector<string> ip;
        split(IPv6, ip, ':');
        if(ip.size() != 8) {
            return false;
        }
        // unordered_set<char> hexs{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f', 'A', 'B', 'C', 'D', 'E', 'F'};
        string hexs{"0123456789abcdefABCDEF"};
        for(auto&& elem : ip) {
            if(elem.empty() || elem.size() > 4) {
                return false;
            }
            // for(char c : elem) {
            //     if(hexs.count(c) == 0) {
            //         return false;
            //     }
            // }
            for(char c : elem) {
                if(hexs.find(c) == string::npos) {
                    return false;
                }
            }
        }
        return true;
    }

    void split(const string& IP, vector<string>& ip, char delim) {
        if(IP.empty()) {
            return;
        }
        stringstream ss(IP);
        string temp;
        while(getline(ss, temp, delim)) {
            ip.emplace_back(move(temp));
        }
        // 处理 IP 地址末尾有一个 '.' 或 ':' 的情况
        if(IP.back() == ':' || IP.back() == '.') {
            ip.push_back("");
        }
    }
};
647. 回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

1
2
3
>输入："abc"
>输出：3
>解释：三个回文子串: "a", "b", "c"

示例 2：

1
2
3
>输入："aaa"
>输出：6
>解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 中心开花
int countSubstrings(string s) {
    int n = s.size();
    int cnt = 0;
    auto palindrome = [&](int left, int right) {
        while(left >= 0 && right < n && s[left] == s[right]) {
            left--;
            right++;
            cnt++;
        }
    };
    for(int i = 0; i < n; i++) {
        palindrome(i, i);
        palindrome(i, i + 1);
    }
    return cnt;
}