算法---字符串

一、算法说明

字符串是一种类型，他不是一种算法，所以我们在处理这方面的问题的时候，需要结合其他的算法

二、题目

最长公共前缀

1、题目

最长公共前缀

2、解题思路

解法一：我们可以先让两个相互比较，然后在将比较出来的公共前缀和下一个作比较

解法二：我们可以一次性比较所有的

3、代码实现

class Solution 
{
public:
    string longestCommonPrefix(vector<string>& strs)
    {
        string r = strs[0];
        for(int i = 1; i<strs.size(); i++)
        {
            r = FindCommmon(r,strs[i]);
        }
        return r;
    }
    string FindCommmon(string& r, string& x)
    {
        int i = 0;
        while(i < min(r.size(), x.size())&&r[i]==x[i])
        {
            i++;
        }
        return r.substr(0,i);
    }
};

最长回文子串

 最长回文子串

（1）题目

（2）解题思路

中心扩展法：我们可以定义一个位子i，然后使用双指针，判断以i为中心的两侧是否相等，分为两种情况，一种是偶数对称即示例2，这是我们双指针的位置分别在 i，和i+1,如果是奇数对称，双指针的位置都在i

（3）代码实现

class Solution
{
public:
    string longestPalindrome(string s) 
    {
        int begin = 0, len = 0;
        for (int i = 0; i < s.size(); i++) 
        {
            int left = i;
            int right = i;
            while (left >=0 && right < s.size() && s[right] == s[left])
            {
                left--;
                right++;
            }
            if (right - left - 1 > len) 
            {
                begin = left + 1;
                len = right - left - 1;
            }
            left = i ; right = i + 1;
            while (left >=0 && right < s.size() && s[right] == s[left])
            {
                left--;
                right++;
            }
             if (right - left - 1 > len) 
            {
                begin = left + 1;
                len = right - left - 1;
            }
        }
        return s.substr(begin, len);
    }
};

字符串相乘

字符串相乘

 （1）题目

（2）解题思路

解题思路一：

1、模拟字符串

添加一个字符串，上面的字符串挨个乘以下面的字符串里面的数字，得到结果后相加

 2、高位相乘的时候，要补上0

   我们可以先将字符串逆序，然后我们会发现下标为几，就在前面加上几个‘0’

3、逆序

等到结果后先全部相加在逆序

4、处理前导’0‘

如果我们乘以的是一个字符'0'只需要保存一个’0‘

解题思路二 ：

（3）代码实现

class Solution 
{
public:
    string multiply(string num1, string num2) 
    {
        
        string ret;
       
        if(num1 == "0" || num2 == "0")
        return "0";
        reverse(num1.begin(),num1.end());
        reverse(num2.begin(),num2.end());
        for(int i = 0 ; i < num1.size(); i++)
        {
            string tmp;
            int k = i;
            while(k--)
            {
                tmp.push_back('0');
            } 
            int add = 0;
            for(int j = 0 ; j < num2.size() ; j++)
            {

                int re = ((num1[i] - '0')*(num2[j] - '0') + add) ;
                add = re/10;
                char s = re%10 + '0';
                tmp.push_back(s);
            }
            if(add!=0)
            {
                tmp.push_back(add+'0');
            }
            ret =  Addstring(tmp , ret);
        } 
        reverse(ret.begin(),ret.end());
        return ret;
    }
     string Addstring(string s1, string s2)
    {
        int i = 0, j = 0, add = 0;
        string ans;
        
        while (i < s1.size() || j < s2.size() || add > 0) {
            int sum = add;
            if (i < s1.size())
                sum += s1[i++] - '0';
            if (j < s2.size())
                sum += s2[j++] - '0';
                
            ans.push_back((sum % 10) + '0');
            add = sum / 10;
        }
        
        return ans;
    }
};