【算法专题十一】字符串

1. leetcode.14.最长公共前缀

1.1 题目

题目链接

1.2 思路

1.3 代码

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

2. leetcode.5.最长回文字串

2.1 题目

题目链接

2.2 思路

2.3 代码

class Solution {
public:
    string longestPalindrome(string s) {
        int begin = 0, len = 0;
        for(int i = 0; i < s.size(); i++)
        {
            // 1. 先做奇数次遍历
            int left = i, right = i;
            while(left >= 0 && right < s.size() && s[left] == s[right])
            {
                left--;
                right++;
                if(right - left - 1 > len)
                {
                    begin = left + 1;
                    len = right - left - 1;
                }
            }
            // 2. 再做偶数次遍历
            left = i, right = i + 1;
            while(left >= 0 && right < s.size() && s[left] == s[right])
            {
                left--;
                right++;
                if(right - left - 1 > len)
                {
                    begin = left + 1;
                    len = right - left - 1;
                }
            }
        }
        return s.substr(begin, len);
    }
};

3. leetcode.67.二进制求和

3.1 题目

题目链接

3.2 思路

3.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 > 0)
        {
            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. leetcode.43.字符串相乘

4.1 题目

题目链接

4.2 思路

4.3 代码

class Solution {
public:
    string multiply(string n1, string n2) {
        // 1. 首先进行 不进位相乘
        int m = n1.size(), n = n2.size();
        reverse(n1.begin(), n1.end());
        reverse(n2.begin(), n2.end());
        vector<int> tmp(m + n - 1);
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');
            }
        }
        // 2. 处理进位
        string ret;
        int cur = 0, t = 0;
        while(cur < m + n - 1 || t != 0)
        {
            if(cur < m + n - 1) t += tmp[cur++];
            ret += t % 10 + '0';
            t /= 10;
        }
        // 3. 处理前导0
        while(ret.size() > 1 && ret.back() == '0') ret.pop_back();
        reverse(ret.begin(), ret.end());
        return ret;
    }
};