算法笔记（八）——字符串

最长公共前缀

题目：最长公共前缀

思路

• 两两比较，将每两个的子串和未比较的字符串相比较；
  

C++代码

class Solution 
{
public:
    string Common(string& s1, string& s2)
    {
        int i = 0;
        while(i < min(s1.size(), s2.size()) && s1[i] == s2[i])
            i++;
        
        return s1.substr(0, i);
    }
    string longestCommonPrefix(vector<string>& strs) 
    {
        // 两两比较
        string ret = strs[0];
        for(int i = 1; i < strs.size(); i++)
            ret = Common(ret, strs[i]);
        
        return ret;
    }
};

最长回文子串

题目：最长回文子串

思路

• 中心扩散：计算以每一个字母为中心向左右两边扩散的奇数和偶数的回文串最大长度和该回文串的起始位置

C++代码

class Solution 
{
public:
    string longestPalindrome(string s) 
    {
        int begin = 0, len = 0;
        int n = s.size();
        for(int i = 0; i < n; i++)
        {
            // 奇数扩展
            int 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);
    }
};

二进制求和

题目：二进制求和

思路

• 从字符串右边开始累加进位拼接字符串，计算完之后记得翻转字符串

C++代码

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

        int cur1 = a.size() - 1;
        int cur2 = b.size() - 1;
        int t = 0; // 进位

        while(cur1 >= 0 || cur2 >= 0 || t)
        {
            if(cur1 >= 0) t += a[cur1--] - '0';
            if(cur2 >= 0) t += b[cur2--] - '0';   
            res += t % 2 + '0';
            t /= 2;
        }
        reverse(res.begin(), res.end());

        return res;
    }
};

字符串相乘

题目：字符串相乘

思路

• 计算两数相乘的时候，先不考虑进位，等到所有结果计算完毕之后再去进位

C++代码

class Solution 
{
public:
    string multiply(string num1, string num2) 
    {
        int n = num1.size(), m = num2.size();

        // 反转两个字符串
        reverse(num1.begin(), num1.end());   
        reverse(num2.begin(), num2.end());   

        // 存放每一位相乘的结果
        vector<int> tmp(n + m - 1);

        // 无进位相乘
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');
            }
        }

        // 处理进位
        int cur = 0, t = 0;
        string ret;
        while(cur < n + m - 1 || t != 0)
        {
            if(cur < n + m + 1) t += tmp[cur++];
            ret += t % 10 + '0';
            t /= 10;
        }

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

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

        return ret;
    }
};