【算法】字符串

引言

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

一、最长公共前缀

思路：

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

class Solution
{
public:
    string longestCommonPrefix(vector<string>& strs)
    {
        if(strs.size() == 0) return "";

        string tmp = strs[0];
        for(int i=1; i<strs.size(); 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<s.size(); 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<int> 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;
    }
};