【算法系列】字符串

leetcode题目

一、最长公共前缀

二、最长回文子串

三、二进制求和

四、字符串相加

五、字符串相乘

六、仅仅反转字母

七、字符串最后一个单词的长度

八、验证回文串

九、反转字符串

十、反转字符串 II

十一、反转字符串中的单词 III

leetcode题目

一、最长公共前缀

14. 最长公共前缀 - 力扣（LeetCode）https://leetcode.cn/problems/longest-common-prefix/1.题目解析

求所有字符串的最长公共前缀

2.算法分析

解法一: 将所有字符串两两比较，求最长公共前缀

解法二: 统一比较所有字符串，当某个字符串的i位置字符不相等，或者i位置在某个字符串中越界，就停止比较，返回结果即可

3.算法代码

解法一:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) 
    {
        string ret = strs[0];
        for(int i = 1; i < strs.size(); i++)
            ret = find_common(ret, strs[i]);
        return ret;
    }

    string find_common(string s1, string s2)
    {
        int i = 0;
        while(i < s1.size() && i < s2.size() && s1[i] == s2[i])
            i++;
        return s1.substr(0, i);
    }
};

解法二:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) 
    {
        for(int i = 0; i < strs[0].size(); i++)
        {
            char tmp = strs[0][i]; //以第一个字符串的字符为基准
            for(int j = 1; j < strs.size(); j++)
                if(i == strs[j].size() || tmp != strs[j][i])
                    return strs[0].substr(0, i);
        }
        return strs[0];
    }
};

二、最长回文子串

5. 最长回文子串 - 力扣（LeetCode）https://leetcode.cn/problems/longest-palindromic-substring/description/1.题目解析

求一个字符串的最长回文子串

2.算法分析

中心扩展算法:

1.固定一个中心点

2.从中心点开始，向两边扩展
注意: 奇数长度以及偶数长度都需要考虑

时间复杂度 O(N^2)

3.算法代码

class Solution {
public:
    string longestPalindrome(string s) 
    {
        int begin = 0, len = 0, n = s.size();
        for(int i = 0; i < n; i++) //1.固定一个中心点
        {
            //2.从中心点开始，向两边扩展
            //2.1 奇数长度的扩展
            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;
            }

            //2.2 偶数长度的扩展
            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);
    }
};

三、二进制求和

1.题目解析

给两个二进制字符串，以二进制字符串形式返回他们的和

2.算法分析

定义两个下标，从字符串结尾开始向前遍历相加，t 存储相加后的结果，注意进位即可~

3.算法代码

class Solution {
public:
    string addBinary(string a, string b) 
    {
        string ret;
        int cur1 = a.size()-1, cur2 = b.size()-1;
        int t = 0;
        while(cur1 >= 0 || cur2 >= 0 || t) //有可能cur1和cur2都走到了空，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;
    }
};

四、字符串相加

415. 字符串相加 - 力扣（LeetCode）https://leetcode.cn/problems/add-strings/1.题目解析

以字符串形式给出两个整数，返回两整数相加之后的字符串形式

2.算法分析

本题与题目三 "二进制求和" 解法是完全一样的，大家参照题目三即可~

3.算法代码

class Solution 
{
public:
    string addStrings(string num1, string num2) 
    {
        int cur1 = num1.size()-1, cur2 = num2.size()-1;
        int t = 0;
        string ret;
        while(cur1 >= 0|| cur2 >= 0 || t)
        {
            if(cur1 >= 0) t += num1[cur1--] - '0';
            if(cur2 >= 0) t += num2[cur2--] - '0';
            ret += t % 10 + '0';
            t /= 10;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

五、字符串相乘

43. 字符串相乘 - 力扣（LeetCode）https://leetcode.cn/problems/multiply-strings/1.题目解析

给定以字符串形式给出的两个非负整数，以字符串形式返回两数的乘积

2.算法分析

解法一：模拟列竖式运算 (也就是我们在演草纸上如何算乘法，就如何写代码即可

解法二：对解法一优化 -> 无进位相乘再相加，最后处理进位

下标的规律: 当计算下标为 i 和下标为 j 的两个数相乘时，最终结果放在下标为 i+j 的位置即可

细节问题:处理前导0，当相乘的两个数字有1个为0时，结果应该是0，但是我们的做法算出来是0000等，因此需要特殊处理

3.算法代码

class Solution {
public:
    string multiply(string n1, string n2) {
        //1.准备工作
        int m = n1.size(), n = n2.size();
        reverse(n1.begin(), n1.end()); //123->321
        reverse(n2.begin(), n2.end()); //456->654
        vector<int> tmp(m+n-1);

        //2.无进位相乘然后相加
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                tmp[i+j] += (n1[i] - '0') * (n2[j] - '0');

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

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

六、仅仅反转字母

917. 仅仅反转字母 - 力扣（LeetCode）https://leetcode.cn/problems/reverse-only-letters/1.题目解析

给定一个字符串，只将字母翻转，其他字符不变

2.算法分析

双指针策略： left从头遍历，right从尾遍历，遍历过程中，遇到非字母，left++, right--, 遇到了字母，就交换即可~

ps: 判断字符是否是字母借助库函数: isalpha

3.算法代码

class Solution {
public:
    string reverseOnlyLetters(string s) 
    {
        size_t left = 0, right = s.size() -1;
        while(left < right)
        {
            while(left < right && !isalpha(s[left]))
                left++;
            while(left < right && !isalpha(s[right]))
                right--;
            swap(s[left], s[right]);
            left++;
            right--;
        }
        return s;
    }
};

七、字符串最后一个单词的长度

字符串最后一个单词的长度_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/8c949ea5f36f422594b306a2300315da?tpId=37&&tqId=21224&rp=5&ru=/activity/oj&qru=/ta/huawei/question-ranking1.题目解析

字符串中的单词以空格分割，求出字符串最后一个单词的长度

2.算法分析

直接调用string类的接口rfind, 从右向左找到第一个空格位置pos即可，用字符串总长度-pos-1

3.算法代码

#include <iostream>
using namespace std;
int main() 
{
    string s;
    while(getline(cin, s))
    {
        int pos = s.rfind(' ');
        cout << s.size() - pos - 1;
    }
    return 0;
}

八、验证回文串

125. 验证回文串 - 力扣（LeetCode）https://leetcode.cn/problems/valid-palindrome/1.题目解析

移除所有的非字母数字字符并且大写转小写之后，正着读和反着读是一样的，则是回文串

2.算法分析

先将所有的大写字母转为小写字母或是将所有的小写字母转为大写字母，然后双指针遍历即可！遍历过程中注意 left < right ，防止越界访问，并且不能加等号, 因为当 s= ",." 时，会出现误判~

3.算法代码

class Solution {
public:
    bool isPalindrome(string s) 
    {
        //大写转小写
        for(auto& e: s)
            e = tolower(e);
        
        //验证回文串
        int left = 0, right = s.size()-1;
        while(left < right)
        {
            while(left < right && !isalpha(s[left]) && !isdigit(s[left])) left++;
            while(left < right && !isalpha(s[right]) && !isdigit(s[right])) right--;
            if(s[left] != s[right]) return false;
            left++, right--;
        }
        return true;
    }
};

九、反转字符串

344. 反转字符串 - 力扣（LeetCode）https://leetcode.cn/problems/reverse-string/description/1.题目解析

反转字符串

2.算法分析

双指针策略

3.算法代码

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0;
        int right = s.size()-1;
        while(left < right)
        {
            swap(s[left], s[right]);
            left++;
            right--;
        }
    }
};

十、反转字符串 II

541. 反转字符串 II - 力扣（LeetCode）https://leetcode.cn/problems/reverse-string-ii/

1.题目解析

每2k个字符翻转前k个字符，如果剩余字符少于k个，则全部反转，如果剩余字符在k到2k之间，则翻转前k个字符，剩余字符保持不变~

2.算法分析

3.算法代码

class Solution {
public:
    string reverseStr(string s, int k) {
        int i= 0;
        while(s.begin()+2*k*i+k < s.end())
        {
            reverse(s.begin()+2*k*i, s.begin()+2*k*i+k);
            i++;
        }
        if(s.begin()+2*k*i < s.end())
            reverse(s.begin()+2*k*i, s.end()); //剩余字符<k个，全部翻转
        return s;
    }
};

十一、反转字符串中的单词 III

557. 反转字符串中的单词 III - 力扣（LeetCode）https://leetcode.cn/problems/reverse-words-in-a-string-iii/

1.题目解析

反转字符串中的所有单词

2.算法分析

使用string提供的find接口，start下标记录一个单词的开始位置，finish下标记录单词结束后的空格位置，用reverse函数对单词进行翻转，start置成下一个单词的开始位置(finish+1), 然后重复上述过程~

3.算法代码

class Solution {
public:
    string reverseWords(string s) {
        size_t start = 0, finish = 0;
        while(finish != s.size())
        {
            finish = s.find(' ', start); //从start位置开始找空格
            if(finish == string::npos) finish = s.size(); //最后一个单词后面没有空格，将finish置成最后一个位置
            reverse(s.begin() + start, s.begin() + finish);
            start = finish + 1; //把start置成下一个单词的第一个位置
        }
        return s;
    }
};