---
# System prepended metadata

title: '**程式筆記(string)**'
tags: [code, string, note]

---

# **程式筆記(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
![image](https://hackmd.io/_uploads/HJIUNBie1e.png =70%x)

* 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(相同字母易序)

![image](https://hackmd.io/_uploads/Bk0x3d3e1l.png =50%x)


```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，是多少次
![image](https://hackmd.io/_uploads/HyMlqZsxJe.png =60%x)

```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
![image](https://hackmd.io/_uploads/Byj4AQilyg.png =80%x)

```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)
跟上一題類似
![image](https://hackmd.io/_uploads/HkPV1Eoxkl.png =60%x)
```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`