算法从入门到精通——字符串

文章目录

• • 本章算法题的简单总结（建议最后看）
  • • 1. 最长回文子串⭐⭐⭐
    • 2. 最长公共前缀⭐
    • 字符串模拟高精度
    • 3. 二进制求和⭐⭐
    • 4. 字符串相乘⭐⭐⭐
• 主标题
• • 1. 最长回文子串⭐⭐⭐
  • • 题目链接：
    • 解题思路
    • 解题代码
    • 大神解题代码
  • 2. 最长公共前缀⭐
  • • 题目链接：
    • 解题思路
    • 解题代码
    • 大神解题代码
  • 3. 二进制求和⭐⭐
  • • 题目链接：
    • 解题思路
    • 解题代码
    • 大神解题代码
    • • 版本一
      • 版本二
  • 4. 字符串相乘⭐⭐⭐
  • • 题目链接：
    • 解题思路
    • 解题代码
    • 大神解题代码
  • 结语

◆ 博主名称：此生决int

大家好，欢迎来到我的博客~

⭐ 个人专栏：快速复习系列

⭐ 热门专栏：蓝桥杯/ACM & 面试算法入门到进阶

文章概要

本文主要介绍了一些字符串常用的一些非常非常基础的技巧，更高级的运用后面博主学会再来与大家分享！

本章算法题的简单总结（建议最后看）

1. 最长回文子串⭐⭐⭐

1，双指针+分类讨论 2。动态规划

2. 最长公共前缀⭐

字符串基础运用

字符串模拟高精度

3. 二进制求和⭐⭐

高精度加法模拟

4. 字符串相乘⭐⭐⭐

模拟高精度乘法

主标题

1. 最长回文子串⭐⭐⭐

题目链接：

最长回文子串

解题思路

本题采用中心扩散法。

回文串具有对称性，因此可以枚举每个位置作为回文中心，然后向两边扩散。

对于一个位置 i：

• 奇数长度回文中心为 (i,i)，例如 "aba"
• 偶数长度回文中心为 (i,i+1)，例如 "abba"

扩散过程中如果左右字符相同，则继续向外扩展；否则停止。

对于每个中心，记录：

• 回文串起点
• 回文串终点
• 回文串长度

最后找到长度最大的回文串并返回即可。

解题代码

class Solution {
//中心扩散
public:
string longestPalindrome(string s) {
int left=0,right=0;
int n=s.size();

//ret[i][0]表示起点
//ret[i][1]表示终点
//ret[i][2]表示长度
vector<vector<int>> ret(n,vector<int>(3));

for(int i=0;i<n;i++)
{
//奇数长度回文
left=right=i;
while(left>=0&&right<n)
{
if(s[left]!=s[right])
break;
left—;
right++;
}

//恢复到最后合法位置
left++;
right—;

ret[i][0]=left;
ret[i][1]=right;
ret[i][2]=right–left+1;

//偶数长度回文
left=i;
right=i+1;

while(left>=0&&right<n)
{
if(s[left]!=s[right])
break;
left—;
right++;
}

//恢复到最后合法位置
left++;
right—;

//如果偶数回文更长则更新
if(right–left+1>ret[i][2])
{
ret[i][0]=left;
ret[i][1]=right;
ret[i][2]=right–left+1;
}
}

//寻找最长回文串
int maxx=0;
for(int i=0;i<n;i++)
if(ret[i][2]>ret[maxx][2])
maxx=i;

return s.substr(ret[maxx][0],ret[maxx][2]);
}
};

没懂？看看大神的解题代码！！

大神解题代码

class Solution {
public:
int start=0;
int maxLen=1;

void expand(string& s,int left,int right)
{
while(left>=0&&right<s.size()&&s[left]==s[right])
{
left—;
right++;
}

//当前回文长度
int len=right–left–1;

//更新答案
if(len>maxLen)
{
maxLen=len;
start=left+1;
}
}

string longestPalindrome(string s) {

for(int i=0;i<s.size();i++)
{
//奇数长度回文
expand(s,i,i);

//偶数长度回文
expand(s,i,i+1);
}

return s.substr(start,maxLen);
}
};

2. 最长公共前缀⭐

题目链接：

最长公共前缀

解题思路

本题采用横向扫描法。

先求出前两个字符串的公共前缀，然后将得到的公共前缀依次与后面的字符串继续求公共前缀。

假设当前公共前缀为 ret：

ret 与 strs[2] 求公共前缀
↓
新的 ret

ret 与 strs[3] 求公共前缀
↓
新的 ret

如果某一步公共前缀变为空串，那么后面无论与谁比较结果都仍然为空串。

因此最终得到的 ret 就是所有字符串的最长公共前缀。

解题代码

class Solution {
public:

//求两个字符串的最长公共前缀
string towlong(string a,string b)
{
string ret;

for(int i=0;i<a.size()&&i<b.size();i++)
{
if(a[i]!=b[i])
return ret;

ret.push_back(a[i]);
}

return ret;
}

string longestCommonPrefix(vector<string>& strs) {

if(strs.size()==1)
return strs[0];

//先求前两个字符串的公共前缀
string ret=towlong(strs[0],strs[1]);

//继续与后面的字符串求公共前缀
for(auto &it:strs)
{
ret=towlong(ret,it);

//已经没有公共前缀了
if(ret.empty())
return "";
}

return ret;
}
};

没懂？看看大神的解题代码！！

大神解题代码

class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {

int i=0;

while(i<strs[0].size())
{
char ch=strs[0][i];

for(auto &s:strs)
{
//越界或字符不同
if(i>=s.size()||s[i]!=ch)
return strs[0].substr(0,i);
}

i++;
}

return strs[0];
}
};

3. 二进制求和⭐⭐

题目链接：

二进制求和

解题思路

由于字符串最低位在末尾，而二进制加法需要从最低位开始计算，因此先将两个字符串翻转。

然后模拟二进制加法，使用 cnt 表示当前进位。

每次取出两个字符串当前位置的数字以及进位相加：

• 和为 0，当前位置放 0，无进位。
• 和为 1，当前位置放 1，无进位。
• 和为 2，当前位置放 0，产生进位。
• 和为 3，当前位置放 1，产生进位。

当较短字符串遍历结束后，继续处理较长字符串剩余的部分，同时考虑进位。

最后如果还有进位，则在结果末尾补一个 1。

由于结果也是逆序存储的，因此最后再翻转一次即可得到答案。

解题代码

class Solution {
public:
string addBinary(string a, string b) {

//翻转，两种情况，进位
string aa=a;
string bb=b;
reverse(aa.begin(),aa.end());
reverse(bb.begin(),bb.end());

string ret;
int cnt=0;
int i=0;

//同时处理两个字符串
while(i<aa.size()&&i<bb.size())
{
int a1=aa[i]–'0';
int a2=bb[i]–'0';
int tmp=a1+a2+cnt;

if(tmp==1)
{
ret.push_back('1');
cnt=0;
}
else if(tmp==0)
{
ret.push_back('0');
cnt=0;
}
else if(tmp==2)
{
ret.push_back('0');
cnt=1;
}
else
{
ret.push_back('1');
cnt=1;
}

i++;
}

//处理a剩余部分
while(i<aa.size())
{
int a1=aa[i]–'0';
int tmp=a1+cnt;

if(tmp==1)
{
ret.push_back('1');
cnt=0;
}
else if(tmp==0)
{
ret.push_back('0');
cnt=0;
}
else
{
ret.push_back('0');
cnt=1;
}

i++;
}

//处理b剩余部分
while(i<bb.size())
{
int a1=bb[i]–'0';
int tmp=a1+cnt;

if(tmp==1)
{
ret.push_back('1');
cnt=0;
}
else if(tmp==0)
{
ret.push_back('0');
cnt=0;
}
else
{
ret.push_back('0');
cnt=1;
}

i++;
}

//最高位还有进位
if(cnt==1)
ret.push_back('1');

//恢复正常顺序
reverse(ret.begin(),ret.end());

return ret;
}
};

没懂？看看大神的解题代码！！

大神解题代码

版本一

class Solution {
public:
string addBinary(string a, string b) {

//翻转字符串，从低位开始计算
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());

string ret;
int t=0;
int i=0;

//模拟二进制加法
while(i<a.size()||i<b.size())
{
if(i<a.size())
t+=a[i]–'0';

if(i<b.size())
t+=b[i]–'0';

//当前位
ret+=to_string(t%2);

//更新进位
t/=2;

i++;
}

//最高位还有进位
if(t==1)
ret.push_back('1');

//恢复正常顺序
reverse(ret.begin(),ret.end());

return ret;
}
};

版本二

class Solution {
public:
string addBinary(string a, string b) {

string ret;

int i=a.size()–1;
int j=b.size()–1;
int carry=0;

while(i>=0||j>=0||carry)
{
if(i>=0)
carry+=a[i—]–'0';

if(j>=0)
carry+=b[j—]–'0';

ret.push_back(carry%2+'0');
carry/=2;
}

reverse(ret.begin(),ret.end());

return ret;
}
};

4. 字符串相乘⭐⭐⭐

题目链接：

字符串相乘

解题思路

由于题目要求不能直接将字符串转换成整数，因此需要模拟竖式乘法。

首先将两个字符串翻转，这样下标 0 就表示个位，方便计算。

设：

• num1[i] 表示第一个数当前位
• num2[j] 表示第二个数当前位

那么它们相乘产生的结果应该累加到：

i + j

位置上。

因此使用数组 arr 保存每一位的结果：

arr[i+j] += (num1[i]-'0') * (num2[j]-'0')

所有位计算完成后，再统一处理进位：

• 当前位保留个位数字。
• 十位及以上加到下一位。

最后去掉高位多余的前导零，再将结果翻转即可得到最终答案。

解题代码

class Solution {
public:
string multiply(string num1, string num2) {

//翻转字符串，方便从低位开始计算
reverse(num1.begin(),num1.end());
reverse(num2.begin(),num2.end());

//arr[i]表示结果第i位
vector<int> arr(num1.size()+num2.size()+1);

//模拟竖式乘法
for(int i=0;i<num1.size();i++)
{
for(int j=0;j<num2.size();j++)
{
arr[i+j]+=(num1[i]–'0')*(num2[j]–'0');
}
}

//统一处理进位
for(int i=0;i<arr.size()–1;i++)
{
arr[i+1]+=arr[i]/10;
arr[i]%=10;
}

//处理前导0
while(arr.size()>1&&arr.back()==0)
arr.pop_back();

string ret;

//转成字符串
for(auto it:arr)
ret+=to_string(it);

//恢复正常顺序
reverse(ret.begin(),ret.end());

return ret;
}
};

没懂？看看大神的解题代码！！

大神解题代码

class Solution {
public:
string multiply(string num1, string num2) {

if(num1=="0"||num2=="0")
return "0";

int n=num1.size();
int m=num2.size();

vector<int> ans(n+m);

for(int i=n–1;i>=0;i—)
{
for(int j=m–1;j>=0;j—)
{
int sum=(num1[i]–'0')*(num2[j]–'0');
sum+=ans[i+j+1];

ans[i+j+1]=sum%10;
ans[i+j]+=sum/10;
}
}

string ret;

int i=0;
while(i<ans.size()&&ans[i]==0)
i++;

while(i<ans.size())
ret.push_back(ans[i++]+'0');

return ret;
}
};

结语

  本期内容就到这里啦，欢迎大家在评论区一起交流讨论

  如果你也在为蓝桥杯/ACM备赛头疼，或是准备算法面试找不到系统学习路径，欢迎订阅我的「算法从入门到精通」专栏！

  这里没有枯燥的理论堆砌，只有完整的算法学习路线， 搭配精选梯度习题+清晰思路解析，帮你把每个算法学透、练熟。包教包会的！

  我们一起在算法路上稳步进阶！