字符串

1.最长公共前缀

法一：两两比较。先比较两个字符串，得到它们的最长公共前缀，再拿这个最长公共前缀与下一个字符串比较，得到新的最长公共前缀。

法二：统一比较。以第一个字符串为基准，比较所有字符串的 i 位置的字符是否一致，如果不一致或 i 越界，则返回strs[0].substr(0,i)。

//法一：两两比较
class Solution {
public:
    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);
    }
    string longestCommonPrefix(vector<string>& strs)
    {
        string ret = strs[0];
        for (int i = 1;i < strs.size();i++)
            ret = FindCommon(ret, strs[i]);
        return ret;
    }
};

//法二：统一比较
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs)
    {
        for (int i = 0;i < strs[0].size();i++)
        {
            char c = strs[0][i];
            for (int j = 1;j < strs.size();j++)
                if (i == strs[j].size() || c != strs[j][i])
                    return strs[0].substr(0, i);
        }
        return strs[0];
    }
};

2.最长回文子串

求回文字符串，可以用中心扩展算法。从某个字符s[i]开始，left、right指针同时向左右两侧移动，当指针未越界且s[left]==s[right]时，left–，right++，两指针停止移动时，两指针之间的区域为回文子串。记录起点pos=left+1，回文子串长度len=right-left-1。left和right同时从 i 位置开始，只能得到奇数长度的字符串，所以当遍历完 i 为中心的奇数长度回文子串后，令left=i，right=i+1，继续遍历 i 为中心的偶数长度回文子串。

class Solution6 {
public:
    string longestPalindrome(string s)
    {
        int n = s.size(), pos = 0, len = 0;
        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)
            {
                pos = 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)
            {
                pos = left + 1;
                len = right - left - 1;
            }
        }
        return s.substr(pos, len);
    }
};

3.二进制求和

这类题属于高精度运算，一般是高精度加法、高精度乘法等。解决此类题只需模拟竖式计算即可。

class Solution {
public:
    string addBinary(string a, string b)
    {
        string ret;
        int cur1 = a.size() - 1, cur2 = b.size() - 1, 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.字符串相乘

法一：模拟竖式计算。与上题类似，需要注意高位相乘时要补0，其中一个乘数为0时结果直接为0，注意最后字符串要逆序。

法二：无进位相乘。在法一的基础上优化，使用无进位相乘，最后处理进位。无进位相乘如下图所示。

字符串先逆置，创建整型数组tmp记录无进位相乘的结果，可以发现规律，tmp的长度为num1.size()+num2.size()-1，每次无进位相乘的结果放在tmp[i+j]，i用来遍历num1，j用来遍历num2。当一个乘数为0时，如123*0，会得到000，此时要处理前导0。由于最终求得的ret是逆序的，此时ret的最后一个元素为最高位，如果最高位为0且ret长度大于1，则说明要处理前导0。

//无进位相乘
class Solution {
public:
    string multiply(string num1, string num2)
    {
        int n1 = num1.size(), n2 = num2.size();
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        vector<int> tmp(n1 + n2 - 1);
		
        //无进位相乘后相加
        for (int i = 0;i < n1;i++)
            for (int j = 0;j < n2;j++)
                tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');
		
        //处理进位
        int cur = 0, t = 0;
        string ret;
        while (cur < n1 + n2 - 1 || t)
        {
            if (cur < n1 + n2 - 1)
                t += tmp[cur++];
            ret += t % 10 + '0';
            t /= 10;
        }

        while (ret.size() > 1 && ret.back() == '0')//处理前导0
            ret.pop_back();
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

//直接模拟竖式计算
class Solution9 {
public:
    string AddString(string a, string b)//字符串相加
    {
        string ret;
        int cur1 = a.size() - 1, cur2 = b.size() - 1, t = 0;
        if (cur1 < 0)
            return b;
        if (cur2 < 0)
            return a;
        while (cur1 >= 0 || cur2 >= 0 || t)
        {
            if (cur1 >= 0)
                t += a[cur1--] - '0';
            if (cur2 >= 0)
                t += b[cur2--] - '0';
            ret += t % 10 + '0';
            t /= 10;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
    
    string multiply(string num1, string num2)//字符串相乘
    {
        string ret;
        int cur1 = num1.size() - 1, cur2 = num2.size() - 1, t = 0;
        if (num1.size() == 1 && num1[cur1] == '0')
            return "0";
        if (num2.size() == 1 && num2[cur2] == '0')
            return "0";

        while (cur1 >= 0)
        {
            string tmp;
            while (cur2 >= 0 || t)
            {
                if (cur2 >= 0)
                    t += (num2[cur2--] - '0') * (num1[cur1] - '0');
                tmp += t % 10 + '0';
                t /= 10;
            }
            reverse(tmp.begin(), tmp.end());
            int n = num1.size() - 1 - cur1;
            while (n--)
                tmp += "0";
            ret = AddString(ret, tmp);
            cur1--;
            cur2 = num2.size() - 1;
        }
        return ret;
    }
};