前言
本文将结合具体题目,进一步深化对于字符串算法的掌握运用。
介绍四种经典字符串算法题目。包括最长公共前缀的两两比较与统一比较解法;最长回文子串的中心拓展算法;二进制求和的模拟竖式计算;以及字符串乘法的大数模拟运算。通过 C++ 代码实现,解析核心思路与边界处理。

本文将结合具体题目,进一步深化对于字符串算法的掌握运用。
现给出字符串数组,要求返回所有字符串的最长公共前缀。
解法一(两两比较): 我们可以先找出前两个的最长公共前缀,然后拿这个最长公共前缀依次与后面的字符串比较,这样就可以找出所有字符串的最长公共前缀。
解法二(统一比较): 题目要求多个字符串的公共前缀,我们可以逐位比较这些字符串,哪一位出现了不同,就在哪一位截止。
两两比较代码示例:
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
// 解法一:两两比较
string ret = strs[0];
for(int i = 1; i < strs.size(); i++)
ret = findCommon(ret, strs[i]);
return ret;
}
string findCommon(string& s1, string& s2){
int i = 0;
while(i < min(s1.size(), s2.size()) && s1[i] == s2[i]) i++;
return s1.substr(0, i);
}
};
统一比较代码示例:
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
// 所有字符串一起 逐个比较
string ret=strs[0];
for(int i=0;i<ret.size();i++){
char temp=strs[0][i];
for(int j=1;j<strs.size();j++){
if(i==strs[j].size()||temp!=strs[j][i]){
return ret.substr(0,i);
}
}
}
return ret;
}
};
题目要求找出字符串 s 中的最长回文子串,我们先来回顾一下什么是回文串。
回文串:即正反形式相同的字符串,例如 aba
本题我们可以采用中心拓展算法。
class Solution {
public:
string longestPalindrome(string s){
int n=s.size();
int left=0,right=0,len=0,begin=0;
for(int i=0;i<n;i++){
// 奇数次拓展
left=i,right=i;
while(left>=0&&right<n&&s[left]==s[right]){
left--; right++;
}
if(right-left-1>len){
begin=left+1; len=right-left-1;
}
// 偶数次拓展
left=i,right=i+1;
while(left>=0&&right<n&&s[left]==s[right]){
left--; right++;
}
if(right-left-1>len){
begin=left+1; len=right-left-1;
}
}
return s.substr(begin,len);
}
};
模拟十进制中我们列竖式计算两个数之和的过程。但是这里是二进制的求和,我们不是逢十进一,而是逢二进一。
class Solution {
public:
string addBinary(string a, string b){
int cur1=a.size()-1,cur2=b.size()-1;
string ret=""; // 返回的字符串
int t=0; // 进位
while(cur1>=0||cur2>=0||t){
if(cur1>=0){
t+=a[cur1--]-'0';
}
if(cur2>=0){
t+=b[cur2--]-'0';
}
ret+=t%2+'0';
t/=2;
}
reverse(ret.begin(),ret.end());
return ret;
}
};
整体思路就是模拟我们小学列竖式计算两个数相乘的过程。但是为了我们书写代码的方便性,我们选择一种优化版本的,就是在计算两数相乘的时候,先不考虑进位,等到所有结果计算完毕之后,再去考虑进位。
class Solution {
public:
string multiply(string num1, string num2){
int m=num1.size(),n=num2.size();
string ret="";
int len=m+n-1;
reverse(num1.begin(),num1.end());
reverse(num2.begin(),num2.end());
// 先逆序两个字符串
// 不进位的乘法
vector<int>temp(len);
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
temp[i+j]+=(num1[i]-'0')*(num2[j]-'0'); // 此处注意是 +=
}
}
// 处理进位
int t=0,cur=0;
while(cur<len||t){
if(cur<len){
t+=temp[cur++];
}
ret+=t%10+'0';
t/=10;
}
// 处理前导 0
while(ret.size()>1&&ret.back()=='0'){
ret.pop_back();
}
reverse(ret.begin(),ret.end());
return ret;
}
};

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online