Featured
刷題刷起來

繼 Array 之後開始 String 類型的題目，一樣是參考網路上已經有整理的 Leetcode 分类顺序表。

參考的頻道或部落格條列如下，提供給大家參考：
ＹＴ：花花醬 / Cspiration 官方频道 / Jacob Huang ／basketwangCoding／今天比昨天厲害／来Offer – LaiOffer／小Q刷Leetcode
Ｂlog：Grandyang／

這篇基本上就是總覽，把解題過程的思路和參考的講解視頻以及其他參考資料都整理在下面。

[2020/10/18] 終於寫完Ｓtring 這個分類，總計４２題：１８Ｅ、１２Ｍ、１２Ｈ，花了三週的時間。說實話比預期的久了不少（一開始還自信滿滿一天要十題）。加上第一部分的Ａrray目前大概交出一個半月一百多題的成績，但這段期間其實一直遇到刷題的倦怠感、出現一些心情的低潮和自我懷疑：刷了這麼多真的有幫助嗎、刷這麼多前面的已經忘了怎麼辦的恐慌等等。但這應該就是成長的必經之路吧，累了就休息一下，充飽電再出發。把不會的一個一個補起來，慢慢的就都會了，相信努力一定會有收穫。

Ｎｏ.完成日期難易度Leetcode Link網路講解視頻Ｍｅｍｏ
12020/09/27Easy28. Implement strStr()Leetcode : 28 Implement strStr 讲解
[LeetCode] 28. Implement strStr() 实现strStr()函数		找出Ａ是否為Ｂ的子字串，若是回傳Ａ在Ｂ的起始位置
直接用兩個ＰＴＲ遍歷，注意一些邊界條件。
1. needle.size() == 0
2. haystack.size()＜needle.size()
2Easy14. Longest Common PrefixLeetcode： 14 Longest Common Prefix 讲解
[LeetCode] 14. Longest Common Prefix 最长共同前缀		找出給定字串的共同最長前綴子字串
１、先將ＬＣＰ指定為第一個字串，接著開始遍歷裡面的字元是否存在其他的每個字串中。
２、另一個方式是排序，這樣最長子字串一定是頭尾兩個的共同子字串。
3Easy58. Length of Last Word[LeetCode] 58. Length of Last Word 求末尾单词的长度找出最後面一個單字的長度
從後往前找，找到 ‘ ’ 就回傳長度，要注意的是要前處理把最後面的空格先去掉。
4.Easy387. First Unique Character in a String[LeetCode] First Unique Character in a String 字符串第一个不同字符找到第一個只出現一次的字元
先掃一遍建Ｍap，再掃一遍看個數是不是只有一個。
5Easy383. Ransom Note給定一勒索信字串，判斷是否可用雜誌字串組出來
建兩個 map，若勒索字元數＞雜誌字元數就不行
6Easy344. Reverse String將一個字串反過來
寫一個 for 迴圈第一個跟最後一個交換，直到遍歷到中間就都換完了。
72020/09/28Medium151. Reverse Words in a String贾考博 LeetCode 151. Reverse Words in a String將一個字串中的單字反過來排，必須忽略空白
先用 while 把最前面和最後面的空白去掉，接著再用ＰＴＲ從後面往前找空白，找到後塞到 ans 中。
8Easy345. Reverse Vowels of a String[LeetCode] Reverse Vowels of a String 翻转字符串中的元音字母翻轉字串中的母音
用 2ptr 從前往後掃，掃到兩個母音就交換。
注意母音大小寫都算，可以
１、寫一個 func 來判斷是否母音
２、用 find_first_of(“aeiouAEIOU”, left)／find_last_of(“aeiouAEIOU”, right)
３、string t = “aeiouAEIOU”; t.find(…)
9Easy205. Isomorphic Strings贾考博 LeetCode 205. Isomorphic Strings 想起化学课
[LeetCode] 205. Isomorphic Strings 同构字符串		給定兩字串，確認是否裡面的字元都是一對一對應
宣告兩個長度 256 的陣列，遍歷兩字串並查找對應的數字是否相同，若不同就結束，相同就更新成ｉ＋１。
10Easy290. Word Pattern[LeetCode] 290. Word Pattern 词语模式判斷單字與 pattern 是否一對一對應
建一個 map 儲存 pattern，若 key 存在，確認 value 是否相同；若 key 不存在，確認是否已存在相同的 value；如果沒有新建對應關係。
最後需確認單字與 pattern 個數是否相同。
istringstream in(str);
string t ; in >> t;
11Easy242. Valid Anagram判斷兩單字是否為字謎（重組後相同）
排序，判斷是否相同。
開兩個 256 的陣列計算每個字元的個數，最後比較是否相同。
122020/09/29Medium49. Group AnagramsLeetcode 49 Group Anagrams 讲解
[LeetCode] 49. Group Anagrams 群组错位词		分類字謎，把重組後相同的排在一起
把每個字串的字元數量當作 Key 分類存到 map 中。
13Medium179. Largest Number贾考博 LeetCode 179. Largest Number 何必呢？將給定的字串排成最大的數字
需要客製化比較函數，比較兩個拼起來之後誰大。
sort(nums.begin(), nums.end(), comp);
14Medium6. ZigZag Conversion[LeetCode]6. ZigZag Conversion 中文
[LeetCode] 6. ZigZag Conversion 之字型转换字符串		把給定字串轉成之字形排序
可以觀察到骨幹部分是以 2*numRows-2 的方式遞增
中間之字形就是 j+2*numRows-2-2*i 的方式遞增
152020/10/03Easy38. Count and Say贾考博 LeetCode 38. Count and Say
[LeetCode] 38. Count and Say 计数和读法		計數和讀法
1 : 1 ； 2: 11 ； 3 : 21
計算前面有幾個一樣的元素，把個數和元素存到下一個字串中
16Hard316. Remove Duplicate Letters小旭讲解 LeetCode 316 Remove Duplicate Letters – EP28
[LeetCode] Remove Duplicate Letters 移除重复字母		刪除重複字母，並且在不打亂原先順序前提下照字母順序排列
使用 stack ＆兩個 HashMap 紀錄出現個數與是否已經放在 stack 中。如果遍歷過就繼續，如果沒遍歷過，判斷 stack 上的是不是比自己大，如果比較大，後面又會出現就 pop 掉。
17Easy168. Excel Sheet Column Title[LeetCode] Excel Sheet Column Title 求Excel表列名称給一個數字求 Excel 表列名稱
從後面往前算，先％２６再／２６，最後輸出答案時反轉即可。
18Easy171. Excel Sheet Column Number[LeetCode] Excel Sheet Column Number 求Excel表列序号給一個 Excel 表列名稱求數字
遍歷字串，相當於２６進位轉１０進位。
19Easy13. Roman to Integer花花酱 LeetCode 13. Roman to Integer – 刷题找工作 EP299
[LeetCode]13. Roman to Integer 中文
[LeetCode] 13. Roman to Integer 罗马数字转化成整数		將羅馬數字轉成整數
可以用一個 Map 先把羅馬字母／數字對應存起來
依序遍歷，若後面大於前面，就把前面的兩倍減掉。
202020/10/04Medium12. Integer to Roman[LeetCode]12. Integer to Roman 中文將整數轉成羅馬數字
先用陣列將所有數字與對應字母存起來，從大往下掃
while(num>=val[i]) {
num-=val[i];
ans.append(sym[i]);
}
21Hard273. Integer to English Words[LeetCode] Integer to English Words 整数转为英文单词將整數轉為英文表達
三個三個一組，分別處理
22Hard68. Text JustificationLeetCode 68. Text Justification 中文解释 Chinese Version
[LeetCode] Text Justification 文本左右对齐		文字左右對齊
首先先判斷一行有幾個單字，接著如果該行是最後一行或是只有一個單字，則只要補到最大行寬。如果不是，那就要計算有幾個空格，然後平均分配。
232020/10/05Hard65. Valid Number[Leetcode 65] Valid Number
[LeetCode] Valid Number 验证数字		判斷是否為有效數字
先把前後的空格去掉，如果只剩一個確認是否為數字
依序處理第一個／中間／最後一個，判斷是否有效
242020/10/07Hard76. Minimum Window Substring[LeetCode]76. Minimum Window Substring 中文最小窗口子字串
使用 sliding window 先找出涵蓋此字串的子字串，再動態調整找出最小範圍。
25Hard30. Substring with Concatenation of All WordsLeetcode : 30. Substring with Concatenation of All Words 讲解
[LeetCode] 30. Substring with Concatenation of All Words 串联所有单词的子串		找出串連所有單詞的子字串
先用一個 map 把所有要找的字串記下來。
接著從頭開始掃，概念有點類似變形的 sliding window。
26Medium3. Longest Substring Without Repeating CharactersLeetcode : 3 Longest Substring Without Repeating Characters 讲解
[LeetCode] 3. Longest Substring Without Repeating Characters 最长无重复字符的子串		找出最長無重複的字串
用一個 map 紀錄每個字元上次出現的位置，如果沒有出現過，或是不在 window 中繼續往右擴張，但如果發現字元已經在目前涵蓋區間中，則將 window 最左邊更新到該字元的下一個位置。每次更新 window 時都紀錄最大值。
27Medium395. Longest Substring with At Least K Repeating Characters【工傅坊：小FU讲解】Leetcode 395. Longest Substring With At Least K Repeating Characters
[LeetCode] 395. Longest Substring with At Least K Repeating Characters 至少有K个重复字符的最长子字符串		找出至少重複Ｋ次的子字串
暴力解把全部子字串切出來，判斷是否字元超過Ｋ次，但超時。
用 Divide And Conquer，先用一個陣列把字元出現數存起來，用小於Ｋ次的地方當切點分兩半，再分別計算回傳左右半邊的最大值。找到切點之後記得再往後找到大於Ｋ次的才是右半邊起始點。
28Easy125. Valid Palindrome[LeetCode] Valid Palindrome 验证回文字符串驗證字串是否回文（需跳過非數字與字母）
isalnum() 可判斷是否為數字＆字母
tolower() 可將字母轉成小寫
使用兩個指針，一直移動到數字＆字母，轉成小寫比較
292020/10/08Medium5. Longest Palindromic Substring[LeetCode]5. Longest Palindromic Substring 中文
[LeetCode] 5. Longest Palindromic Substring 最长回文子串		最長回文子字串
用 dp[i][j] 紀錄ｉ～ｊ是否回文，則可寫出ＤＰ方程
i = j : true
j = i + 1：if 兩字元相同則回文
j = i + n：if 兩字元相同且 dp[i+1][j-1] 是回文
最後紀錄最長回文字串起始與長度

另一個是馬拉車算法，待研究。
30Easy9. Palindrome Number[LeetCode] 9. Palindrome Number 验证回文数字驗證數字是否回文
只要是負數就一定不是，把 int 轉成 string，判斷是否回文。
Follow up 不能用字串，可以直接把數字倒過來，相等就是回文。
312020/10/11Hard214. Shortest Palindrome花花酱 LeetCode 214. Shortest Palindrome
[LeetCode] 214. Shortest Palindrome 最短回文串		最短回文字串
在給定字串前加上字符讓他成為最短回文字串。
將給定的字串Ｓ反轉得到Ｔ，一個從頭一個從尾取Ｎ−１～１個，當相等時表示找到最長回文字串，只要再加上前面沒有重複的即可。

另一個是ＫＭＰ算法，待研究。
32Hard336. Palindrome Pairs[LeetCode] Palindrome Pairs 回文对給定一字串陣列，找出組起來是回文的組合
先用一 Map 存字串與 Index 的對應，遍歷每個字串先找到是否有反轉後相等且不是同樣位置的字串；接著在找是否存在反轉子字串且剩餘部分回文。
33Medium131. Palindrome Partitioning贾考博 LeetCode 131. Palindrome Partitioning
[LeetCode] Palindrome Partitioning 拆分回文串		給定一字串，找出切開之後是回文的地方
這題可以用 Backtracking 的方式枚舉所有可能性，當遇到回文的時候繼續往下遍歷。
34Hard132. Palindrome Partitioning II花花酱 LeetCode 132. Palindrome Partitioning II – 刷题找工作 EP281
[LeetCode] Palindrome Partitioning II 拆分回文串之二		給定一字串，求出切開之後是回文的最少刀數
這題需要兩個ＤＰ陣列，一個紀錄ｊ－ｉ是否是回文，一個紀錄前ｉ個的最小刀數是多少。當ｊ－ｉ是回文時，取前ｊ−１的最小刀數＋１和目前紀錄的最小值。當Ｊ＝０表是從頭開始到目前都是回文，刀數＝０。
35Easy20. Valid Parentheses[LeetCode] 20. Valid Parentheses 验证括号驗證括號是否有效
（［｛｝］）需成對出現，右括號也必須在左括號後面。
這題直接用 Stack來解，遇到左邊的就放進去，遇到右邊的就看Ｓ是否為空或是最上面那個是否跟他成對。
362020/10/12Medium22. Generate ParenthesesLeetcode : 22 Generate Parentheses 讲解
贾考博 LeetCode 22. Generate Parentheses		生成所有有效的括號組
這題也是用 Backtracking 來枚舉，當左右都＝０則到達最後邊界可以直接加入答案，需要注意的是左括號數量＜右括號不合法。
37Hard32. Longest Valid ParenthesesLeetcode : 32. Longest Valid Parentheses 讲解
[LeetCode] 32. Longest Valid Parentheses 最长有效括号		最長有效括號組
用 Stack 來解，並宣告一個變數存起始位置。當遇到左括號就壓入棧中，若在 Stack 為空情況下遇到右括號，更新起始位置。不然就把棧內的 pop 出來，紀錄最長有效括號長度。
382020/10/13Medium241. Different Ways to Add Parentheses花花酱 LeetCode 241. Different Ways to Add Parentheses – 刷题找工作 EP32
[LeetCode] 241. Different Ways to Add Parentheses 添加括号的不同方式		添加括號的不同方式：給定一字串之後算出不同括號排列下的值
這題可以在運算符的地方用遞迴切開左右半邊遍歷求解，當最後只有數字就把字串轉述自存進去，然後再把左右半邊的和根據運算符計算出來，過程中可以把求過的紀錄在 Map 裡節省重複運算的時間。
39Hard301. Remove Invalid Parentheses花花酱 LeetCode 301. Remove Invalid Parentheses – 刷题找工作 EP139
[LeetCode] 301. Remove Invalid Parentheses 移除非法括号		移除非法括號
先掃一遍計算不合法的左括號＆右括號個數
接著遞歸先把右括號刪掉，再刪左括號，當左右括號都刪光光時判斷是否為合法解。
40Easy392. Is Subsequence[LeetCode] Is Subsequence 是子序列判斷一字串是否是另一個字串的子序列
使用兩個ＰＴＲ指向Ｓ／Ｔ，如果兩個字元相等就都加一，不然只有Ｔ的往前移動，最後判斷Ｓ指針是否已經找到終點。
另一個方式是先將Ｔ中所有字元的位置存到 HashMap 中，在搜尋時用 pre 把Ｓ在Ｔ中的位置記錄下來，後面必須大於前面才是合法。
41Hard115. Distinct Subsequences花花酱 LeetCode 115. Distinct Subsequences – 刷题找工作 EP208
[LeetCode] 115. Distinct Subsequences 不同的子序列		不同的子序列，給定Ｓ找出可以從中找出幾組子序列Ｔ
給定兩個ＸＸＸ，求ＸＸＸ，通常用ＤＰ解
找到動態轉移方程：如果字元相同則 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]，不然直接等於 dp[i-1][j]
422010/10/18Medium187. Repeated DNA Sequences贾考博 LeetCode 187. Repeated DNA Sequences 有这样的DNA应该是活不了太久了
[LeetCode] 187. Repeated DNA Sequences 求重复的DNA序列		重複的ＤＮＡ序列
求重複的ＤＮＡ子序列，用 Map 來紀錄出現次數，如果超過兩次就放入解答中。利用ＡＴＧＣ最後三 bit 值會不同的特性，可以用一個整數來存１０個字元，如此一來即可節省使用空間。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料。