一、最长公共前缀
1.方法一：横向扫描
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (!strs.size()) {
return "";
}
string prefix = strs[0];
int count = strs.size();
for (int i = 1; i < count; ++i) {
prefix = longestCommonPrefix(prefix, strs[i]);
if (!prefix.size()) {
break;
}
}
return prefix;
}
string longestCommonPrefix(const string& str1, const string& str2) {
int length = min(str1.size(), str2.size());
int index = 0;
while (index < length && str1[index] == str2[index]) {
++index;
}
return str1.substr(0, index);
}
};
解释
（1）return str1.substr(0, index)
使用了 substr() 方法从一个字符串中提取子字符串。
substr() 方法接受两个参数。第一个参数是子字符串的起始索引，第二个参数是子字符串的长度。这段代码从 str1 字符串的开头提取了一个子字符串，直到（但不包括）位于 index 位置的字符，并将该子字符串作为新字符串返回。
2.方法二：纵向扫描
方法一是横向扫描，依次遍历每个字符串，更新最长公共前缀。另一种方法是纵向扫描。纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (!strs.size()) {
return "";
}
int length = strs[0].size();
int count = strs.size();
for (int i = 0; i < length; ++i) {
char c = strs[0][i];
for (int j = 1; j < count; ++j) {
if (i == strs[j].size() || strs[j][i] != c) {
return strs[0].substr(0, i);
}
}
}
return strs[0];
}
};
3.方法三：分治
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (!strs.size()) {
return "";
}
else {
return longestCommonPrefix(strs, 0, strs.size() - 1);
}
}
string longestCommonPrefix(const vector<string>& strs, int start, int end) {
if (start == end) {
return strs[start];
}
else {
int mid = (start + end) / 2;
string lcpLeft = longestCommonPrefix(strs, start, mid);
string lcpRight = longestCommonPrefix(strs, mid + 1, end);
return commonPrefix(lcpLeft, lcpRight);
}
}
string commonPrefix(const string& lcpLeft, const string& lcpRight) {
int minLength = min(lcpLeft.size(), lcpRight.size());
for (int i = 0; i < minLength; ++i) {
if (lcpLeft[i] != lcpRight[i]) {
return lcpLeft.substr(0, i);
}
}
return lcpLeft.substr(0, minLength);
}
};
4.方法四：二分查找
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (!strs.size()) {
return "";
}
int minLength = min_element(strs.begin(), strs.end(), [](const string& s, const string& t) {return s.size() < t.size();})->size();
int low = 0, high = minLength;
while (low < high) {
int mid = (high - low + 1) / 2 + low;
if (isCommonPrefix(strs, mid)) {
low = mid;
}
else {
high = mid - 1;
}
}
return strs[0].substr(0, low);
}
bool isCommonPrefix(const vector<string>& strs, int length) {
string str0 = strs[0].substr(0, length);
int count = strs.size();
for (int i = 1; i < count; ++i) {
string str = strs[i];
for (int j = 0; j < length; ++j) {
if (str0[j] != str[j]) {
return false;
}
}
}
return true;
}
};
解析:
(1)min_element(strs.begin(), strs.end(), [](const string& s, const string& t) {return s.size() < t.size();})->size();
min_element函数的参数是一个迭代器范围，由strs.begin()和strs.end()表示，这意味着要查找整个字符串向量中的最小元素。
第三个参数是一个函数对象，它是一个lambda表达式，用于指定如何比较两个字符串的大小。在这个lambda表达式中，const string& s和const string& t表示要比较的两个字符串，return s.size() < t.size()表示按照字符串长度从小到大进行比较。也就是说，这个lambda表达式将两个字符串的长度作为比较的关键字，返回值为两个字符串的长度比较结果。
最后，min_element函数返回一个迭代器，该迭代器指向字符串向量中的最小元素，即长度最短的字符串。因此，在这个代码中，->size()被用来获取长度最短的字符串的长度，并将其作为函数的返回值返回。
二、最长回文字串
方法一：动态规划
动态规划算法的实现通常分为四个步骤：定义状态、设计状态转移方程、初始化边界状态、计算最终状态。其中状态定义是最关键的一步，它需要将原问题转化为一个适合动态规划求解的子问题形式。状态转移方程则是核心步骤，它需要根据子问题之间的关系设计出一种递推公式，用来更新子问题的解。边界状态则是指最简单的子问题，通常需要先进行初始化。最终状态则是指原问题的解，通常可以通过已经求解过的子问题的解来计算得出。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// dp[i][j] 表示 s[i..j] 是否是回文串
vector<vector<int>> dp(n, vector<int>(n));
// 初始化：所有长度为 1 的子串都是回文串
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// 递推开始
// 先枚举子串长度
for (int L = 2; L <= n; L++) {
// 枚举左边界，左边界的上限设置可以宽松一些
for (int i = 0; i < n; i++) {
// 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
int j = L + i - 1;
// 如果右边界越界，就可以退出当前循环
if (j >= n) {
break;
}
if (s[i] != s[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substr(begin, maxLen);
}
};
方法二：中心扩展算法
class Solution {
public:
pair<int, int> expandAroundCenter(const string& s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
--left;
++right;
}
return {left + 1, right - 1};
}
string longestPalindrome(string s) {
int start = 0, end = 0;
for (int i = 0; i < s.size(); ++i) {
auto [left1, right1] = expandAroundCenter(s, i, i);
auto [left2, right2] = expandAroundCenter(s, i, i + 1);
if (right1 - left1 > end - start) {
start = left1;
end = right1;
}
if (right2 - left2 > end - start) {
start = left2;
end = right2;
}
}
return s.substr(start, end - start + 1);
}
};
三、翻转字符串里的单词
方法一：自行编写对应的函数
class Solution {
public:
string reverseWords(string s) {
// 反转整个字符串
reverse(s.begin(), s.end());
int n = s.size();
int idx = 0;
for (int start = 0; start < n; ++start) {
if (s[start] != ' ') {
// 填一个空白字符然后将idx移动到下一个单词的开头位置
if (idx != 0) s[idx++] = ' ';
// 循环遍历至单词的末尾
int end = start;
while (end < n && s[end] != ' ') s[idx++] = s[end++];
// 反转整个单词
reverse(s.begin() + idx - (end - start), s.begin() + idx);
// 更新start，去找下一个单词
start = end;
}
}
//s.erase(s.begin() + idx, s.end()) 的含义是，删除从第一个多余空 //格到字符串末尾的所有元素，包括第一个多余空格。
s.erase(s.begin() + idx, s.end());
return s;
}
};
方法二：双端队列
class Solution {
public:
string reverseWords(string s) {
int left = 0, right = s.size() - 1;
// 去掉字符串开头的空白字符
while (left <= right && s[left] == ' ') ++left;
// 去掉字符串末尾的空白字符
while (left <= right && s[right] == ' ') --right;
//定义了一个名为 d 的双端队列（deque），其中存储的元素是字符串（string）类型。
deque<string> d;
string word;
while (left <= right) {
char c = s[left];
if (word.size() && c == ' ') {
// 将单词 push 到队列的头部
d.push_front(move(word));
word = "";
}
else if (c != ' ') {
word += c;
}
++left;
}
//将最后一个单词添加到双端队列 d 的头部
d.push_front(move(word));
string ans;
while (!d.empty()) {
ans += d.front();
d.pop_front();
if (!d.empty()) ans += ' ';
}
return ans;
}
};
四、字符串匹配算法：KMP
给定两个串S=“s1s2s3 …sn”和T=“t1t2t3 …tn”，在主串S中寻找子串T的过程叫做模式匹配，T称为模式。KMP算法是一种字符串模式匹配算法。
方法1： 暴力匹配（朴素模式匹配BF）
规定i是主串S的下标，j是模式T的下标。现在假设现在主串S匹配到 i 位置，模式串T匹配到 j 位置。
如果当前字符匹配成功（即S[i] = T[j]），则i++，j++，继续匹配下一个字符；如果失配（即S[i] != T[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯到本次失配起始字符的下一个字符，j 回溯到0。
代码：
int BF(char S[],char T[])
{
int i=0,j=0;
while(S[i]!='\0'&&T[j]!='\0')
{
if(S[i]==T[j])
{
i++;
j++;
}
else
{
i=i-j+1;
j=0;
}
}
if(T[j]=='\0') return (i-j); //主串中存在该模式返回下标号
else return -1; //主串中不存在该模式
}
思路分析：
现在有主串S：ababcabcacbab，模式串T：abcac。我们来看一下是如何匹配的。i从0开始，j也从0开始。
(1)在第一次匹配中，i从0开始，j从0开始。当i=2，j=2时匹配失败，此时i回溯到1，j回溯到0。
(2)第二次匹配中，i从1开始，j从0开始。当i=1，j=0时匹配失败，此时i回溯到2，j回溯到0。
(3)第三次匹配中，i从2开始，j从0开始。当i=6，j=4时匹配失败，此时i回溯到3，j回溯到0。
(4)第四次匹配中，i从3开始，j从0开始。当i=3，j=0时匹配失败，此时i回溯到4，j回溯到0。
(5)第五次匹配中，i从4开始，j从0开始。当i=4，j=0时匹配失败，此时i回溯到5，j回溯到0。
(6)第六次匹配中，i从5开始，j从0开始。i=10，j=5，T中全部字符比较完，匹配成功，返回本次匹配起始位置下标i - j。（i=9和j=4的时候匹配成功，i和j会再加一次，所以i=10，j=5）.
可见，如果i已经匹配了一段字符后出现了失配的情况，i会重新往回回溯，j又从0开始比较。这样浪费的大量的时间。在第三次匹配结束后，我们可以发现：i=3和j=0，i=4和j=0以及i=5和j=0是不必进行的，因为从第三次部分匹配过程中我们可以得出，主串中第3，4，5个字符必然是‘b’，‘c’，‘a’（即与模式串的第1，2，3个字符分别对应相等），而模式的首字符是‘a’，它分别与‘b’，‘c’不等，与‘a’相等。如果将模式向右滑动3个字符继续进行i=6和j=1时的字符比较，很明显会加快进程。这样就引出了我们的KMP算法，不回溯i，加快匹配效率。
方法2：KMP算法
(1)算法内容
KMP算法又称克努特-莫里斯-普拉特操作。它的改进在于：每当从某个起始位置开始一趟比较后，在匹配过程中出现失配，不回溯i，而是利用已经得到的部分匹配结果，将一种假想的位置定位“指针”在模式上向右滑动尽可能远的一段距离到某个位置后，继续按规则进行下一次的比较。
(2)算法流程
规定i是主串S的下标，j是模式T的下标。现在假设现在主串S匹配到 i 位置，模式串T匹配到 j 位置。
(1)如果j = -1，则i++，j++，继续匹配下一个字符；
(2)如果S[i] = T[j]，则i++，j++，继续匹配下一个字符；
(3)如果j != -1，且S[i] != P[j]，则 i 不变，j = next[j]。此举意味着失配时，接下来模式串T要相对于主串S向右移动j - next [j] 位。
int KMP(int start,char S[],char T[])
{
int i=start,j=0;
while(S[i]!='\0'&&T[j]!='\0')
{
// j==-1 是为了避免在模式串的第一个字符就不匹配的情况下出现数组越界的情况。
if(j==-1||S[i]==T[j])
{
i++; //继续对下一个字符比较
j++; //模式串向右滑动
}
else j=next[j];
}
if(T[j]=='\0') return (i-j); //匹配成功返回下标
else return -1; //匹配失败返回-1
}
解释：
1.前后缀
假设有一个串P=“p0p1p2 …pj-1pj”。如果存在p0p1…pk-1pk = pj-kpj-k+1…pj-1pj，我们就说在P串中有一个最大长度为k+1的公共前后缀。
注：
(1)找前缀时，要找除了最后一个字符的所有子串。
(2)找后缀时，要找除了第一个字符的所有子串。
现在有串P=abaabca，各个子串的最大公共前后缀长度如下表所示：
这样，公共前后缀最长长度就会和串P的每个字符产生一种对应关系：
这个表的含义是在当前字符作为最后一个字符时，当前子串所拥有的公共前后缀最长长度。例如当c作为最后一个字符时，当前子串abaabc并没有公共前后缀。
2.next数组
接下来我们就用这个表来引出next数组，next 数组的值是除当前字符外（注意不包括当前字符）的公共前后缀最长长度，相当于把上表做一个变形，将表中公共前后缀最长长度全部右移一位，第一个值赋为-1。例如c对应next值的意义是，c之前（不包括c）的子串abaab所拥有的公共前后缀最长长度为2，我们称next数组中的值为失效函数值，也就是c的失效函数值为2。
(3)算法思路
现在有主串S：ababcabcacbab，模式串T：abcac。i从0开始，j也从0开始。根据上述方法可以知道，T的中每个字符对应的失效函数值为：
(1)第一次匹配中，i从0开始，j从0开始。当i=2，j=2时匹配失败，此时i不动，next[j]=next[2]=0，接下来模式串T要相对于主串S向右移动j - next [j] = 2 位，j回溯到0。
(2)第二次匹配中，i从2开始，j从0开始。当i=6，j=4时匹配失败，此时i不动，next[j]=next[4]=1，接下来模式串T要相对于主串S向右移动j - next [j] = 3位，j回溯到1。
(3)第三次匹配中，i从6开始，j从1开始。当i=10，j=5时匹配成功，返回i - j = 5。
当主串S与模式串P失配时，j=next[j]，P向右移动j - next[j]。也就是当模式串P后缀pj-kpj-k+1…pj-1与主串S的si-ksi-k+1…si-1匹配成功，但是pj和si失配时，因为next[j]=k，相当于在不包含pj的模式串中有最大长度为k的相同前后缀，也就是p0p1…pk-1 = pj-kpj-k+1…pj-1，所以令j = next[j]，让模式串右移j - next[j]位，使模式串p0p1…pk-1 与主串si-ksi-k+1…si-1对齐，让pk和si继续匹配。如下图所示：
KMP的next数组告诉我们：当模式串中的某个字符跟主串中的某个字符失配时，模式串下一步应该跳到哪个位置。如模式串中在j 处的字符跟主串在i 处的字符匹配失配时，下一步用next [j] 处的字符继续跟主串i 处的字符匹配，相当于模式串向右移动 j - next[j] 位。
4.递推求next数组
我们很容易的可以知道，next[0] = -1。next[1] = 0也是容易推得的。假定我们给定了某模式串，且已知next[j] = k，现在求得next[j+1]等于多少。我们分两种情况分析：
(1)当pk=pj时，next[j + 1] = next[j] + 1 = k + 1，代表字符E前的模式串中，有长度k+1 的最大公共前后缀。
(2)当pk ! = pj时，说明p0p1…pk-1pk != pj-kpj-k+1…pj-1pj，这时ABC与ABD不相同，也就是字符E前的模式串中没有长度为k+1的最大公共前后缀，所以next[j + 1] = next[j] + 1不再适用，我们只能寻找更短的最大公共前后缀。
这样看来，如果我们能在p0p1…pk-1pk中不断递归索引k = next[k]，找到一个字符pk’，也是D的话，那么最大公共前后缀长度就为k’+1。此时pk’=pj，且p0p1…pk’-1pk’ = pj-k’pj-k’+1…pj-1pj。从而next[j+1] = k’ + 1 = next[k’] + 1。否则前缀没有D，next[j+1] = 0。
在pk != pj时，k = next[k]，用pnext[k]去跟pj继续匹配。为什么不用其他值和pj匹配呢？我们可以看到，在pj之前，有一段长度为k的已匹配串；在pk之前有一段蓝色的已匹配串，说明pk字符前有一段长度为next[k]的最大公共前后缀（蓝色的那段）。如果pk != pj，说明p0p1…pk-1pk != pj-kpj-k+1…pj-1pj，那么我们只能找更短的最大公共前后缀，此时因为pk和pnext[k]前面的蓝色串已完全匹配，如果pnext[k]能和pj匹配 ，那么我们便找到了我们需要的串。如果还是不匹配，下一步pnext[next[k]…]去跟pj继续匹配,直到找到长度更短公共前后缀。
求next数组的递推代码：
void GetNext(char T[])
{
int j=0,k=-1;
next[j]=k;
while(T[j]!='\0')
{
if(k==-1||T[j]==T[k])
{
j++;
k++;
next[j]=k;
}
else k=next[k];
}
}
其实，我们在分析的过程中可以发现，k=next[next[k]…]这一步其实非常的类似于递归。因此我们也给出递归的代码供读者参考。
int GetNext(int j,char T[])
{
if(j==0)return -1;
if(j>0)
{
int k=GetNext(j-1,T);
while(k>=0)
{
if(T[j-1]==T[k])return k+1;
else k=GetNext(k,T);
}
return 0;
}
return 0;
}
五、实现 strStr()
方法一：暴力匹配
c
int strStr(char* haystack, char* needle) {
int n = strlen(haystack), m = strlen(needle);
for (int i = 0; i + m <= n; i++) {
bool flag = true;
for (int j = 0; j < m; j++) {
if (haystack[i + j] != needle[j]) {
flag = false;
break;
}
}
if (flag) {
return i;
}
}
return -1;
}
c++
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size(), m = needle.size();
for (int i = 0; i + m <= n; i++) {
bool flag = true;
for (int j = 0; j < m; j++) {
if (haystack[i + j] != needle[j]) {
flag = false;
break;
}
}
if (flag) {
return i;
}
}
return -1;
}
};
