文章目录

• 引言
• 一、最长公共前缀
• 二、最长回文子串
• 三、二进制求和
• 四、字符串相乘

引言

字符串题，大多数是模拟题，或者考察其他算法。通过本专题，了解字符串题型的函数接口和常用做法。

一、最长公共前缀

思路：

1. 先处理边界，数组为空，返回空串
2. 先用字符串tmp存储第一个字符串，再与其他字符串两两比较，保留相同的部分
3. 比较完后，最后保留下来的tmp，即为最长公共前缀

class Solution { public:     string longestCommonPrefix(vector& strs)     {         if(strs.size() == 0) return "";          string tmp = strs[0];         for(int i=1; i             int cur = 0;             while(cur < tmp.size() && cur < strs[i].size() && tmp[cur] == strs[i][cur])             {                 cur++;             }             tmp.resize(cur);         }         return tmp;     } }; 

二、最长回文子串

思路：

1. 中心扩展算法：暴力解法的优化，利用了回文串对称的性质进行枚举
2. 遍历字符串，对于每一个位置，分别进行奇数长度和偶数长度的枚举，分别进行结果更新
3. 注意遍历的过程中，只记录起始位置和长度，最后再创建子串

class Solution { public:     string longestPalindrome(string s)     {         int pos = 0, len = 0;         for(int i=0; i             int left1 = i, right1 = i;//奇数个             while(left1 >= 0 && right1 < s.size() && s[left1] == s[right1])             {                 left1--;                 right1++;             }             if(right1 - left1 - 1 > len)             {                 pos = left1 + 1;                 len = right1 - left1 - 1;             }              int left2 = i, right2 = i + 1;//偶数个             while(left2 >= 0 && right2 < s.size() && s[left2] == s[right2])             {                 left2--;                 right2++;             }             if(right2 - left2 - 1 > len)             {                 pos = left2 + 1;                 len = right2 - left2 - 1;             }         }         return s.substr(pos, len);     } }; 

三、二进制求和

思路：

1. 高精度加法
2. 分别从两个字符串的尾部开始向前遍历，模拟列竖式的过程
3. 如果cur1、cur2存在，则取出对应位置的数字，否则返回0
4. 将取出的数字与进位相加，再进行取模和整除操作，更新结果字符串和进位
5. 循环条件：两个字符串没遍历完或者进位不为0，只要有一个满足，则循环继续
6. 最后逆置字符串，返回

class Solution { public:     string addBinary(string a, string b)     {         string s;         int cur1 = a.size() - 1, cur2 = b.size() - 1, carry = 0;         while(cur1 >= 0 || cur2 >= 0 || carry)         {             int n1 = cur1 >= 0 ? a[cur1--] - '0' : 0;             int n2 = cur2 >= 0 ? b[cur2--] - '0' : 0;             int n = n1 + n2 + carry;              s += n % 2 + '0';             carry = n / 2;         }          reverse(s.begin(), s.end());         return s;     } }; 

四、字符串相乘

思路：

1. 高精度乘法
2. 先无进位相乘，再处理进位，最后处理前导零
3. 无进位相乘：开辟tmp数组，大小为m + n - 1，分别从两个字符串的尾部开始向前遍历，对应下标i + j，进行无进位相乘
4. 处理进位：从后向前遍历tmp数组，处理进位的同时更新结果字符串
5. 处理前导零：当结果字符串长度大于1，且尾部为零，尾删
6. 逆置字符串，返回

class Solution { public:     string multiply(string n1, string n2)     {         //无进位相乘         int m = n1.size(), n = n2.size();         vector tmp(m + n - 1);         for(int i=m-1; i>=0; i--)         {             for(int j=n-1; j>=0; j--)             {                 tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');             }         }         //处理进位         string s;         int cur = m + n - 2, carry = 0;         while(cur >= 0 || carry)         {             if(cur >= 0) carry += tmp[cur--];             s += carry % 10 + '0';             carry /= 10;         }         //去除前导零         while(s.size() > 1 && s.back() == '0') s.pop_back();         //逆序         reverse(s.begin(), s.end());         return s;     } };