字符串的各类问题

文章参考自[算法总结] 13 道题搞定 BAT 面试——字符串

一、匹配

1.1 字符串之间的匹配

考虑到KMP算法等均偏复杂且众所周知，不太可能会要求上机书写，因此应着重理解算法的各类思想，并能够流畅清晰阐述。

1.1.1 KMP

由于暴力匹配的方法会反复回溯主串，导致效率低下，而KMP算法可以利用已经部分匹配这个有效信息，保证主串上的指针不回溯，仅通过修改模式串上的指针，让模式串尽可能地移动到有效的位置。 具体来讲，假设当前文本串S匹配到i位置，模式串P匹配到j位置。若 j == -1 或匹配已成功，都令i+1, j+1尝试继续匹配下一位置。若 j!= -1 且当前位置匹配失败，则保持i不变，使 j = next[j]，即匹配串相对于文本串向右移动了 j - next[j]位。其中，next数组隐含了当前字符之前的字符串中，有多大长度的相同前缀后缀。因此，若能求得next数组，便可充分利用已部分匹配这一信息。

匹配字符串

计算next数组时，我们可以直接寻找模式串中最大长度的前缀和后缀，基于长度求得next数组。程序计算next数组时，则最好采用递归的思想，利用已经求得的一部分next数组计算新的next值。即对于 next[j+1]，若P[k] == P[j]， 则next[j+1] = next[j] + 1 = k + 1。否则应递归使得 k = next[k] 再进行此判断。递归的思想实际上是基于next数组本身的含义，使得我们可以直接在next[k]之前寻找长度更短的相同前缀后缀。

算法的详细描述可参见此处。

next数组的优化 考虑到匹配时，模式串若出现p[j] = p[next[j]]的情况，则必定发生再次回溯。因此可在求next数组时，即令next[j] = next[k]回溯一次。

设文本串长度为n，模式串长度为m，算法的时间复杂度为O(m+n)空间复杂度为O(m)

1.1.2 BM算法

BM算法基于坏字符规则和好后缀规则，效率更高。详细描述可参见这里。

坏字符规则：字符不匹配时，模式串后移位数 = 坏字符的位置 - 模式串中的上一次出现位置。

好后缀规则：后移位数 = 好后缀的位置 - 模式串中好后缀上一次出现的位置。

若无上一次出现的位置，即仅出现一次，则“上一次出现的位置”置为-1.

算法初始将模式串与文本串头部对齐，每次均从尾部开始比较，需要进行移动时，取两个规则中的较大值。

好后缀规则需要注意的地方

(1) "好后缀"的位置以最后一个字符为准。假定"ABCDEF"的"EF"是好后缀，则它的位置以"F"为准，即5（从0开始计算）。 (2) 如果"好后缀"在搜索词中只出现一次，则它的上一次出现位置为 -1。比如，"EF"在"ABCDEF"之中只出现一次，则它的上一次出现位置为-1（即未出现）。 (3) 如果"好后缀"有多个，则除了最长的那个"好后缀"，其他"好后缀"的上一次出现位置必须在头部。比如，假定"BABCDAB"的"好后缀"是"DAB"、"AB"、"B"，请问这时"好后缀"的上一次出现位置是什么？回答是，此时采用的好后缀是"B"，它的上一次出现位置是头部，即第0位。这个规则也可以这样表达：如果最长的那个"好后缀"只出现一次，则可以把搜索词改写成如下形式进行位置计算"(DA)BABCDAB"，即虚拟加入最前面的"DA"。

算法应首先求得坏字符数组和好后缀数组。预处理时间复杂度O(m + σ),其中σ为字母表容量。在最坏情况下拥有O(mn)的时间复杂度，最好的情况是O(n/m)。

Describe BM Algorithm in English

The Boyer-Moore string-search algorithm is an efficient string-searching algorithm that is the standard benchmark for practical string-search literature. The algorithm preprocesses the pattern string instead of the string being searched in. The BM algorithm uses information during preprocess and it can skip along the text in jumps of multiple characters rather than searching every single character in the text. Specifically speaking, the start of pattern string will be aligned with the start of text string at the beginning. Characters are then compared from the end of pattern string, moving backward. If a mismatch occurs, the alignment will be shifted forward according to the maximum value permitted by several rules. The comparisons will be performed again at the new alignment. A shift is calculated by applying two rules: the bad character rule and the good suffix rule. The bad character rule considers the character at which the comparision process failed. The next occurrence of that character to the left is found, and a shift which brings that occurrence with the mismatched occurrence is proposed. Whereas the good suffix rule considers the suffix that has been matched and a shift which brings the occerrence with the matched occurrence is proposed. The BM algorithm has worst-case running time of O(nm), and the best-case running time is O(n/m). Generally speaking, the algorithm run faster as the pattern length increases.

1.1.3 Sunday算法

md Sunday算法是真的厉害

Sunday算法在开始匹配的时候仍然是将头部对齐，但从前端开始匹配，若出现匹配失败，要考虑文本串中参与匹配的最末尾字符的下一位字符在模式串中的位置，将两者对齐再进行匹配。

Sunday算法易于理解且速度快，但容易出现O(mn)的情况。

1.2 简单正则表达式的匹配

实现一个函数用来匹配包括’.’和’’的正则表达式。模式中的字符’.’表示任意一个字符，而’’表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配

注意此题并没有括号，且只有两种模式符号，因此应当可以不用动态规划，分情况判断即可。

二、子串

2.1 最长不重复子串

Leetcode第三题 直接穷举的话复杂度肯定会很高，而初次写就想到使用Map也不是很容易，尤其是Map的value可以不断变化的想法。

public int lengthOfLongestSubstring(String s) {
        int result = 0;
        int currentStart = 0;
        HashMap<Character, Integer> infoMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            if (infoMap.containsKey(s.charAt(i))) {
                currentStart = Math.max(infoMap.get(s.charAt(i)) + 1, currentStart);
            }
            infoMap.put(s.charAt(i), i);
            result = Math.max(result, i - currentStart + 1);
        }
        return result;
    }

2.2 字符串数组中最长公共前缀

Leetcode第十四题

虽然是easy难度，但比较有意思。比较直接的想法肯定是设置一个指针，每次尝试移动一个位置，但这样每次都要扫描全组字符串，复杂度应该能达到O(nm)了。

分治法、二分查找之类的思想都可以考虑，但应该都没有有效降低复杂度，因为这些思想都涉及到扫描每一个字符串。以下思想明显更为巧妙且降低复杂度，只不过要基于每个字符串的长度在O(1)内获得。

Leetcode之所以设为easy难度大抵在于O(nm)也可以过。

2.3 最长回文串

LeetCode第409题

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串

观察一下，还是比较容易想到的，回文串除了中间的一个字符两端都需要是偶数个。

2.4 最长回文子串/子序列

动态规划的典型问题。

对于最长回文子串，中心扩展法可用，且空间复杂度更低。

采用动态规划，对于 $i, j\in[0, len(str))$ 需设定F[i][j]为从下标i至j的子串是否为回文串，随后有下列递推关系。

$$F[i][j] = \begin{cases} true, \quad i=j \\\\ c[i] == c[j], \quad j=i+1 \\\\ c[i] == c[j]\ and\ f(i+1, j-1), \quad j>i+1 \end{cases}$$

// 最长回文子串
int maxPalin(string str)
{
    vector<vector<bool>> f(str.size(), vector<bool>(str.size(), false));
    int resultMax = 0;
    f[0][0] = true;
    for(int j = 1; j < str.size(); j++)
    {
        // 单个字符一定是回文串
        f[j][j] = true;
        for(int i = 0; i < j; i++)
        {
            f[i][j] = (str[i] == str[j] && (j == i + 1 || f[i + 1][j - 1]));
            if(f[i][j])
                resultMax = max(resultMax, j - i + 1);
        }
    }
    return resultMax;
}

最长回文子序列

此时数组中存放的应该就是从i到j最长回文子序列的长度了。考虑到对于回文串，左右两边各新增一个字符时，新的串若仍是回文的话，须使得新增的两个字符相同。因此形成如下递推关系。

$$F[i][j] = \begin{cases} 1, \quad i=j \\\\ 2, \quad j=i+1\ and\ c[i] == c[j] \\\\ f(i+1, j-1) + 2, \quad j>i+1\ and\ c[i] == c[j] \\\\ max(f(i+1, j),\ f(i, j-1)),\quad c[i]\ !=\ c[j] \end{cases}$$

int maxPalinSubSeq(string str)
{
    vector<vector<int>> f(str.size(), vector<int>(str.size(), 1));
    for(int i = str.size() - 1; i >= 0; i--)
    {
        for(int j = i + 1; j < str.size(); j++)
        {
            if(j == i + 1 && str[i] == str[j])
                f[i][j] = 2;
            else if(str[i] == str[j])
                f[i][j] = f[i + 1][j - 1] + 2;
            else
                f[i][j] = max(f[i + 1][j], f[i][j - 1]);
        }
    }
    return f[0][str.size() - 1];
}

三、变换

3.1 字符串的排列子串问题

Leetcode第567题

一个字符串的排列是否是另一个字符串的子串

考虑到模式串的某一排列在文本串内的出现必定是连续的，连续的这一段各个字符的出现次数必定是与模式串一致的。因此可统计模式串内各个字符的出现次数，利用双指针扫描文本串内的一段即可。未经优化的话，复杂度应该达到了O(nm)，不过就这就能过了。

// 3.1 字符串的排列是否是另一字符串的子串
bool permutationInStr(string pattern, string text)
{
    if(pattern.size() > text.size() || pattern == "") {
        return false;
    }
    vector<int> patternCountMap(128, 0);
    for(char& eachC : pattern) {
        patternCountMap[eachC]++;
    }
    vector<int> textCurrentCountMap(128, 0);
    unsigned int left = 0;
    unsigned int right = pattern.size() - 1;
    for(int i = left; i <= right; i++) {
        textCurrentCountMap[text[i]]++;
    }
    if(patternCountMap == textCurrentCountMap) {
        return true;
    }
    while(right + 1 < text.size()) {
        textCurrentCountMap[text[left]]--;
        left++;
        right++;
        textCurrentCountMap[text[right]]++;
        if(patternCountMap == textCurrentCountMap) {
            return true;
        }
    }
    return false;
}

3.2 求字符串的全排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

首先，字典序的要求可以在完成全部排列后进行一次排序。使用递归进行排列时，要注意每次是将第一个字符与后边各个与其不相同的字符分别交换一次，交换后即形成一次不同的排列，针对后续的字符进行一次递归调用。

// 字符串的全排列
vector<string> result;
void allPermutationHelper(string str, unsigned int currentStart);
void allPermutation(string str) {
    result.clear();
    allPermutationHelper(str, 0);

    sort(result.begin(), result.end());
    copy(result.begin(), result.end(), ostream_iterator<string>{std::cout, "\n"});
}

void allPermutationHelper(string str, unsigned int currentStart) {
    if (currentStart == str.size() - 1) {
        result.push_back(str);
        return;
    }
    for (unsigned int j = currentStart; j < str.size(); j++) {
        if(j != currentStart && str[currentStart] == str[j]) {
            continue;
        }
        swap(str[j], str[currentStart]);
        allPermutationHelper(str, currentStart + 1);
        swap(str[j], str[currentStart]);
    }
}

3.3 翻转字符串中的全部单词

Leetcode 第151题

用Java的话就会非常简单，使用C++的话关键是写出正确的split， 题目要求C++的必须空间复杂度O(1), md

// 3.3 翻转字符串中的全部单词
string reverseWords(string s) {
    string result;
    for(int i = 0;i < s.size(); i++) {
        if(s[i] == ' ') {
            continue;
        }
        int nextPos = s.find(" ", i);
        if(nextPos != string::npos) {
        // 注意起始的空格
        // 其实可以考虑最后移掉多余的空格
            if(result.size() > 0) {
                result = s.substr(i,  nextPos - i) + " " + result;
            } else {
                result = s.substr(i,  nextPos - i);
            }
            i = s.find(" ", i);
        } else {
            if(result.size() > 0) {
                result = s.substr(i,  nextPos - i) + " " + result;
            } else {
                result = s.substr(i,  nextPos - i);
            }
            break;
        }
    }
    return result;
}

3.4 旋转字符串

Leetcode第796题

两个字符串 A 和 B。 A 的旋转操作就是将 A 最左边的字符移动到最右边。 例如, 若 A = 'abcde'，在移动一次之后结果就是'bcdea' 。如果在若干次旋转操作之后，A 能变成B，那么返回True。

大不了一个一个试，复杂度$O(n^2)$，然而其实拼起来子串寻找下就行了....

// 3.4 旋转字符串
bool rotateString(string A, string B) {
    return A.size() == B.size() && ((A + A).find(B) != string::npos);
}

3.5 parseInt

转换为整数没啥难度，注意长度为0以及正负号就可以了。