# **程式筆記(string)**
:::info
:information_source: 日期 : 2023/06/26
:::
**:star2:** 基本操作
* 把list變成string
```python
lst = ["a", "b"]
res = "".join(lst)
res # "ab"
```
* 把string拆分成list
```python
s = " hello world "
s = s.split() # 自動跳過前後空白格
s # ['hello', 'world']
```
* 檢查char屬性
```python
c = "12345"
print(c.isdigit()) # 輸出: True
*判斷正數
c = "hello"
print(c.isalpha()) # 輸出: True
```
* ASCII
```python
# 字母轉ascii
ascii_value = ord('a') # 97
# ascii轉字母
char = chr(97) # 'a'
str = [0] * 26
for c in s:
str[ord(c) - ord("a")] = 1
```
```python
ord('a') <= ord(char) <= ord('z') -> 97 - 122
ord('A') <= ord(char) <= ord('Z') -> 65 - 90
ord('0') <= ord(char) <= ord('9') -> 48 - 57
```
* 大小寫
```python
法1.
s = "HELLO WORLD"
s_lower = s.lower() # 輸出: "hello world"
法2.
c = 'A'
c_lower = chr(ord(c) + 32)
```
* tuple
```python
tuple沒有add之類的功能，因為不可變
("a","b")和("b","a")不同
```
* 數字轉成str遍歷
```python
temp = 12
for c in str(temp):
print(c) # '1', '2'
```
**:star2:** 基本題解
* Valid Palindrome(回文)
先去除non-alphanumeric，最後用two-pointer解Palindrome
* Group Anagrams
```python
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
record = collections.defaultdict(list)
for s in strs:
s_ascii = [0] * 26
for c in s:
s_ascii[ord(c) - ord("a")] += 1
record[tuple(s_ascii)].append(s)
return list(record.values())
```
* Valid Anagram(相同字母易序)
```python
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
dict_s, dict_t = {}, {}
for c in s:
dict_s[c] = 1 + dict_s.get(c, 0)
for c in t:
dict_t[c] = 1 + dict_t.get(c, 0)
for c in dict_s:
if c in dict_t and dict_t[c] == dict_s[c]:
continue
else:
return False
return True
```
* String Compression
```
把["a","a","b","b","c","c","c"]
轉成["a","2","b","2","c","3"]
```
```python
class Solution:
def compress(self, chars: List[str]) -> int:
n = len(chars)
l, r = 0, 0
i = 0
while r < n :
temp = 0
while r < n and chars[l] == chars[r]:
r += 1
chars[i] = chars[l]
i += 1
# 可以把數字轉換成str遍歷
temp = r - l
if temp == 1:
pass
else:
for c in str(temp):
chars[i] = c
i += 1
l = r
return i
```
* Reverse Words in a String
s = " hello world "
Output: "world hello"
```python
class Solution:
def reverseWords(self, s: str) -> str:
s = s.split()
res = []
for i in range(len(s) - 1, -1, -1):
res.append(s[i])
return " ".join(res)
```
---
**:star2:** sliding window 之 計算長度
毛毛蟲移動法(用於substring)，前頭碰到一樣的就收後尾
```python
while r < len(s):
while s[r] in visited:
visited.remove(s[l])
l += 1
visited.add(s[r])
maxLen = max(maxLen, r - l + 1)
r += 1
```
* Longest Substring Without Repeating Characters
```python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
maxLen = 0
l, r = 0, 0
visited = set()
while r < len(s):
while s[r] in visited:
visited.remove(s[l])
l += 1
visited.add(s[r])
maxLen = max(maxLen, r - l + 1)
r += 1
return maxLen
```
* Longest Repeating Character Replacement
當這段區間的非最高頻字母大於k時(dict紀錄)，必須移動後尾去縮小長度(記得同時要刪除dict內的後尾次數)
最高頻字次數 max(record.values())
```python
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
maxLen = 0
l, r = 0, 0
record = collections.defaultdict(int)
while r < len(s):
record[s[r]] += 1
maxFreq = max(record.values())
while (r - l + 1) - maxFreq > k:
record[s[l]] -= 1
l += 1
maxLen = max(maxLen, r - l + 1)
r += 1
return maxLen
```
* Maximum Number of Vowels in a Substring of Given Length
給定一長度k(window大小)，window內出現最多次aeiou，是多少次
```python
class Solution:
def maxVowels(self, s: str, k: int) -> int:
maxN = 0
l, r = 0, 0
count = 0
while r < len(s):
if r - l + 1 > k:
if s[l] in "aeiou":
count -= 1
l += 1
if s[r] in "aeiou":
count += 1
maxN = max(maxN, count)
r += 1
return maxN
```
---
**:star2:** sliding window 之 Palindromic
用 l, r = i, i 和 l, r = i, i + 1
* Longest Palindromic Substring
```python
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
maxLen = float("-inf")
maxRes = ""
for i in range(n):
l, r = i, i
while l >= 0 and r < n and s[l] == s[r]:
if maxLen < (r - l + 1):
maxLen = r - l + 1
maxRes = s[l : r + 1]
l -= 1
r += 1
l, r = i, i + 1
while l >= 0 and r < n and s[l] == s[r]:
if maxLen < (r - l + 1):
maxLen = r - l + 1
maxRes = s[l : r + 1]
l -= 1
r += 1
return maxRes
```
* Palindromic Substrings(總共Palindromic)
跟上一題類似
```python
class Solution:
def countSubstrings(self, s: str) -> int:
# 想法 : 類似上一題的解法(也是分兩層)
total = 0
for i in range(len(s)):
l, r = i, i
while l >= 0 and r < len(s) and self.isPalindromic(l, r, s):
total += 1
l -= 1
r += 1
l, r = i, i + 1
while l >= 0 and r < len(s) and self.isPalindromic(l, r, s):
total += 1
l -= 1
r += 1
return total
```
---
**:star2:** sliding window 之 兩字串互動
用dict去紀錄字母出現次數
* Minimum Window Substring
用兩個dict紀錄出現的字，need為dictT，have為某字的dictS == dictT字母+數量相等，當have == need 進入毛毛蟲法
```
s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
```
```python
class Solution:
def minWindow(self, s: str, t: str) -> str:
dictS, dictT = collections.defaultdict(int), collections.defaultdict(int)
for c in t:
dictT[c] += 1
need, have = len(dictT), 0
l, r = 0, 0
minLen = float("inf")
resl, resr = 0, 0
while r < len(s):
dictS[s[r]] += 1
if s[r] in dictT and dictT[s[r]] == dictS[s[r]]:
have += 1
while need == have:
if minLen > (r - l + 1):
minLen = (r - l + 1)
resl, resr = l, r
# 收後腿
dictS[s[l]] -= 1
# 檢查條件(收到不該收的)
if s[l] in dictT and dictT[s[l]] > dictS[s[l]]:
have -= 1
l += 1
r += 1
return s[resl : resr + 1] if minLen != float("inf") else ""
```
* Find All Anagrams in a String
```
Example 1:
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
```
```python
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
n, m = len(p), len(s)
if m < n:
return []
dictS, dictP = defaultdict(int), defaultdict(int)
for i in range(n):
dictS[s[i]] += 1
dictP[p[i]] += 1
l, r = 0, n - 1
res = []
while r < m:
if dictS == dictP:
res.append(l)
dictS[s[l]] -= 1
if dictS[s[l]] == 0:
del dictS[s[l]]
l += 1
r += 1
if r != m:
dictS[s[r]] += 1
return res
```
---
**講解連結**
Provided by. hard working me
###### tags: `string` `note` `code`
Sign in with Wallet
Connect another wallet