關(guān)于字符串操作

這類題一般是和其它算法合起來，比如模擬，雙指針，動態(tài)規(guī)劃或者回溯等，所以字符串相關(guān)的題目類型一般是非常非常豐富的，這里我們選取幾道經(jīng)典的題目進行講解

部分OJ題詳解

14. 最長公共前綴

14. 最長公共前綴 - 力扣（LeetCode）

題目題意還是很簡單的，就是返回單詞的公共前綴，沒有公共前綴就返回空，下面來分析下這道題：

• 解法一：兩兩比較，找公共前綴；假設(shè)有四個字符串，分成三組，每兩組找公共前綴，然后再兩個前綴再找公共前綴，最終結(jié)果就是所有字符串的公共前綴，這道題我們主要就是解決“如何找到兩個字符串的公共前綴”，很簡單，定義兩個指針即可
• 解法二：統(tǒng)一比較；就是定義一個指針，然后一次性比較所有字符串的前綴，當(dāng)有空或者有一個字符不一樣，停止遍歷，返回結(jié)果。

解法一：?

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {string ret = strs[0];for(int i = 1; i < strs.size(); i++)ret = findCommon(ret, strs[i]);return ret; }string findCommon(string s1, string s2){int i = 0;while(i < min(s1.size(), s2.size()) && s1[i] == s2[i]) i++;//i是遍歷兩個字符串的指針，所以i的大小必須小于等于最短的那個字符串，不然會越界訪問return s1.substr(0, i);}
};

解法二：

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {for(int i = 0; i < strs[0].size(); i++) //我們可以先以第一個字符串為基準(zhǔn)，后面再做判斷{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. 最長回文字串

5. 最長回文子串 - 力扣（LeetCode）

題目要我們找出一個字符串s中的最長回文字串，其中這個字串是一串連續(xù)的字串，下面我們來分析下這道題：

• 解法：中心擴展算法；這個算法的本質(zhì)還是暴力枚舉，但是這里是利用了回文串的特性來做枚舉的，比正常枚舉要快
• 我們先固定一個位置，假設(shè)為i，然后定義兩個指針，向前向后移動，因為如果是回文，左邊和右邊的字符是對稱的，所以指針移動的時候，如果指針指向的值相同，就繼續(xù)移動，如果不一樣了，記錄結(jié)果
• 但是這樣只能找奇數(shù)的回文字串，偶數(shù)的找不了，所以我們固定i，先left = right找奇數(shù)找一次，然后再right = left + 1，再找偶數(shù)找一次，就能把奇數(shù)偶數(shù)全找到
• 步驟：1，固定一個中心點? ? 2，從中心開始，向兩邊擴展，奇數(shù)偶數(shù)各找一次

class Solution {
public:string longestPalindrome(string s) {int begin = 0, len = 0; for(int i = 0; i < s.size(); i++) //依次枚舉所有的中點{//先找奇數(shù)的擴展int left = i, right = i;while(left >= 0 && right < s.size()){if(s[left] == s[right]){left--;right++;}elsebreak;}if(right - left - 1 > len){begin = left + 1;len = right - left - 1;}//再做偶數(shù)的擴展left = i, right = left + 1;while(left >= 0 && right < s.size()){if(s[left] == s[right]){left--;right++;}elsebreak;}if(right - left - 1 > len){begin = left + 1;len = right - left - 1;}}    return s.substr(begin, len);}
};

67. 二進制求和

67. 二進制求和 - 力扣（LeetCode）

這個題目是一道經(jīng)典的算法題，用到的算法是“高精度加法”，而同樣的還是高精度減法，乘法和觸發(fā)。而高精度顧名思義就是一個數(shù)實在是太大，平常的數(shù)據(jù)類型存不下，然后我們要對這種很大的數(shù)字進行運算，用到的算法就是“高精度運算”

下面我們來分析下這道題：

• 解法：模擬列豎式運算。這道題和我們鏈表章節(jié)的“兩數(shù)相加”那個題目很相似，我們定義一個t = 0記錄相加的結(jié)果，具體步驟和鏈表的“兩數(shù)相加”很像：算法學(xué)習(xí)（八） —— 鏈表-CSDN博客
• 

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;}
};

43. 字符串相乘

43. 字符串相乘 - 力扣（LeetCode）

這一題用到的就是我們上一題提到的“高精度乘法”這個算法，題目很簡單，就是把字符串的值相乘，注意不能使用stoi和to_string等字符串整型轉(zhuǎn)換函數(shù)，因為這時題目要求的，下面來解釋下這道題：

• 解法一：模擬列豎式運算；步驟一：單獨拿nums2的一位和num1相乘? ? 步驟而：再把所有的結(jié)果累加起來。
• 細(xì)節(jié)一：高位相乘的時候，要補0? ? ?細(xì)節(jié)二：處理前導(dǎo)0? ? 細(xì)節(jié)三：注意計算結(jié)果的順序（可以看到解法一思路很簡單，但是細(xì)節(jié)很多很多，稍不注意就會出錯，所以解法一的代碼不太好寫）
• 解法二：對解法一做優(yōu)化 --> 五進位相乘再相加，最后處理進位
• 
• 對于步驟②，我們可以搞一個數(shù)組int[m + n - 1] tmp，m是num1的程度，n是num2的長度，然后我們就可以直接相加，因為同一列算出來的數(shù)存進數(shù)組時，下標(biāo)是一樣的，可以直接相加
• 對于步驟③，就是處理進位，就是遍歷一次數(shù)組，然后一邊累加再放到最終字符串ret里
• 細(xì)節(jié)：處理前導(dǎo)零?

?解法一的代碼太復(fù)雜就不寫了，我們直接用解法二來寫：

class Solution {
public:string multiply(string num1, string num2) {//解法二：無進位相乘然后相加，最后處理進位//1，準(zhǔn)備工作reverse(num1.begin(), num1.end());    reverse(num2.begin(), num2.end()); //逆序是為了方便處理前導(dǎo)零int m = num1.size(), n = num2.size();vector<int> tmp(m + n - 1); //存儲步驟②的結(jié)果，順便實現(xiàn)相加//2，無進位相乘再相加for(int i = 0; i < m; i++){for(int j = 0; j < n; j++)tmp[i + j] += ((num1[i] - '0') * (num2[j] - '0'));}//3，處理進位int cur = 0, t = 0; //cur遍歷數(shù)組，t表示進位string ret; //存儲最終結(jié)果while(cur < m + n - 1 || t != 0){if(cur < m + n - 1) t += tmp[cur++];ret += (t % 10) + '0';t /= 10;}//4，處理前導(dǎo)零while(ret.size() > 1 && ret.back() == '0') ret.pop_back();reverse(ret.begin(), ret.end());return ret;}
};