14. 最長公共前綴

14. 最長公共前綴

? 編寫一個函數來查找字符串數組中的最長公共前綴。

? 如果不存在公共前綴，返回空字符串 ""。

示例 1：

輸入：strs = ["flower","flow","flight"]
輸出："fl"

示例 2：

輸入：strs = ["dog","racecar","car"]
輸出：""
解釋：輸入不存在公共前綴。

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 僅由小寫英文字母組成

---

解題思路：模擬

? 這道題模擬的思路有兩種，第一種就是每次比較每個字符串同一位置的字符，判斷是否相等，如果不相等則返回前面匹配的位置，可以使用 substr() 函數直接實現這塊！

? 另一種思路就是兩兩字符串進行比較，得到一個最長公共前綴之后，將其與第三個字符串比較，以此類推直到比較了所有字符串之后，得到的結果就是最長的公共前綴了！

? 兩種思路的時間復雜度都是 O(n*m)，其中 n 表示的是字符串的個數，m 表示字符串平均字符個數，下面代碼我們采用的是第一種思路！

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()) || (strs[j][i] != tmp))return strs[0].substr(0, i);}}return strs[0];}
};

5. 最長回文子串

5. 最長回文子串

? 給你一個字符串 s，找到 s 中最長的回文子串。

? 如果字符串的反序與原始字符串相同，則該字符串稱為回文字符串。

示例 1：

輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案。

示例 2：

輸入：s = "cbbd"
輸出："bb"

提示：

• 1 <= s.length <= 1000
• s 僅由數字和英文字母組成

---

解題思路一：動態規劃

? 這道題的動態規劃解法之前在學動態規劃的時候就已經講過了，這里就不再贅述了，具體可以參考之前的筆記！

class Solution {
public:string longestPalindrome(string s) {// 定義dp二維數組，dp[j][i]表示從[j, i]區間是否為回文字符串bool dp[1000][1000] = { 0 };int maxlen = 0, maxindex = 0;for(int i = 0; i < s.size(); ++i){for(int j = 0; j <= i; ++j){// 狀態轉移方程if(s[i] == s[j]){if(i == j || j + 1 == i)dp[j][i] = true;elsedp[j][i] = dp[j + 1][i - 1];if(dp[j][i] && i - j + 1 > maxlen) // 是回文字符串并且長度更長了再更新{maxlen = i - j + 1;maxindex = j;}}}}return s.substr(maxindex, maxlen);}
};

解題思路二：中心擴散法

? 之前我們在動態規劃筆記中提到，字符串的常見題解方法還有一個中心擴散法（至于一個馬拉車算法就不講了，學習成本高，使用率太低），它其實借助的就是回文字符串的特性，由中心自發的向外擴散尋找回文字符串，直到不符合要求！

? 假設此時我們遍歷到字符串的 i 位置，然后定義兩個指針 left 和 right 指向該位置，兩指針從該位置分別向左和向右出發，每次走一格，判斷 s[left] 是否等于 s[right]，是的話說明此時就是 [left, right] 區間就是一個回文字符串，則判斷是否需要更新最大長度以及回文字符串的起始位置，一直重復上述動作直到判斷不符合或者越界了為止！

? 但是上面操作有個問題，就是只考慮到了區間是奇數的情況，如果是偶數情況比如字符串 "abbc" 的話，此時 "bb" 這種情況就被忽略了，所以我們 需要判斷偶數個字符的情況！

class Solution {
public:string longestPalindrome(string s) {int n = s.size();int maxlen = 0, maxindex = 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 > maxlen){maxlen = right - left - 1;maxindex = left + 1;}// 判斷偶數情況（就起始位置不一樣，剩下的操作邏輯都是一樣的）left = i, right = i + 1;while(left >= 0 && right < n && s[left] == s[right]){left--;right++;}if(right - left - 1 > maxlen){maxlen = right - left - 1;maxindex = left + 1;}}return s.substr(maxindex, maxlen);}
};