字符串算法进阶：公共前缀、回文子串与大数运算

第二章：最长回文子串

2.1 题目链接

LeetCode 最长回文子串

2.2 题目分析

题目要求找出字符串 s 中的最长回文子串，我们先来回顾一下什么是回文串。

回文串：即正反形式相同的字符串，例如 aba

2.3 思路讲解

本题我们可以采用中心拓展算法。

• 对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。如此这样去除，一直除到长度小于等于 2 时呢？长度为 1 的，自身与自身就构成回文；而长度为 2 的，就要判断这两个字符是否相等了。
• 从这个性质可以反推出来，从回文串的中心开始，往左读和往右读也是一样的。那么，是否可以枚举回文串的中心呢？
• 从中心向两边扩展，如果两边的字母相同，我们就可以继续扩展；如果不同，我们就停止扩展。
• 这样只需要一层 for 循环，我们就可以完成先前两层 for 循环的工作量。

2.4 代码实现

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);
    }
};

第三章：二进制求和

3.1 题目链接

LeetCode 二进制求和

3.2 题目分析

• 题目给出两个只包含二进制数字的字符串，要求返回其按二进制运算规则相加的和
• 该和用字符串表示

3.3 思路讲解

模拟十进制中我们列竖式计算两个数之和的过程。但是这里是二进制的求和，我们不是逢十进一，而是逢二进一。

3.4 代码实现

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;
    }
};

第四章：字符串乘法

4.1 题目链接

LeetCode 字符串乘法

4.2 题目分析

• 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
• 观察字符串长度范围，首先排除正常乘法，因为其值大小远超 long long 所能表示的范围

4.3 思路讲解

整体思路就是模拟我们小学列竖式计算两个数相乘的过程。但是为了我们书写代码的方便性，我们选择一种优化版本的，就是在计算两数相乘的时候，先不考虑进位，等到所有结果计算完毕之后，再去考虑进位。

4.4 代码实现

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;
    }
};