String

Posted on Edited on In ,

Data structure of string.

Workshop Notes

useful functions

  • str.startswith(prefix)
  • str.endswith(suffix)
  • str.find(sub)
  • str.replace(old, new)
  • str.split(sep)
    Reference from: Minnie’s workshop

Some methods

  • Recursive - for palindromic
  • DP - Usually a little complex
  • Sliding window - Two pointers

Samples

Palindromic Substring

No.5 - Longest Palindromic Substring
Expand Around Center - $O(n^2)$

1
2
3
4
5
6
7
8
9
def helper(s, i, j):
    if i >= 0 and j < len(s) and s[i] == s[j]:
        return helper(s, i-1, j+1)
    else:
        return s[i+1: j]

for i in range(len(s)):
    helper(s, i, i)
    helper(s, i, i+1)

DP - $O(n^2)$
$$P(i, i) = True$$
$$P(i, i+1) = S(i) == S(i+1)$$
$$P(i, j) = P(i+1, j-1) and S(i) == S(j)$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ans = [0, 0]
for i in range(len(s)):
    dp[i][i] = True
    if i + 1 < len(s):
        dp[i][i+1] = s[i] == s[i+1]
        if dp[i][i+1]:
            ans[0], ans[1] = i, i+1

for j in range(2, len(s)):
    for i in range(0, len(s)):
        idx1, idx2 = i, i + j
        if idx1 + 1 < len(s) and idx2 < len(s): 
            dp[idx1][idx2] = dp[idx1+1][idx2-1] and s[idx1] == s[idx2]
            if dp[idx1][idx2] and idx2 - idx1 + 1> ans[1] - ans[0]:
                ans[0], ans[1] = idx1, idx2
                
return s[ans[0]: ans[1] + 1]

No.125 - Valid Palindrome

Substring

No.3 - Longest Substring Without Repeating Characters
Sliding window, HashTable to record the index

1
2
3
4
5
6
7
8
9
10
dic = {}
max_len = 0
i, j = 0, 0
while j < len(s):
    if s[j] in dic:
        i = max(dic[s[j]] + 1, i)
    dic[s[j]] = j
    max_len = max(max_len, j - i + 1)
    j += 1
return max_len

No.340 - Longest Substring with At Most K Distinct Characters
Sliding window, Hashtable to record the rightest index of the character

1
2
3
4
5
6
7
8
9
10
11
12
max_len = 0
left, right = 0, 0
dic = {}
while right < len(s):
    if s[right] not in dic and len(dic.keys()) >= k:
        left = min(dic.values())
        dic.pop(s[left])
        left += 1
    dic[s[right]] = right
    max_len = max(max_len, right - left + 1)
    right += 1
return max_len

DP - dp[i] means the shortest substring with at most k distinct characters if you must use s[i], therefore, we have
$s[i] = s[i - 1] + 1$ if there is no more than k distinct characters from bg to i
$s[i] = i - bg_new$ where bg_new is where there are only k distince characters from bg_new to i

No.76 - Minimum Window Substring

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def minWindow(self, s: str, t: str) -> str:
    form_t = collections.Counter(t)
    current_cnt, target = 0, len(form_t)
    dic_cnt = {}
    left, right = 0, 0
    min_len = s + t
    while right < len(s):
        if s[right] in form_t:
            dic_cnt[s[right]] = dic_cnt.get(s[right], 0) + 1
            if dic_cnt[s[right]] == form_t[s[right]]:
                current_cnt += 1
        while current_cnt == target:
            if s[left] in form_t:
                dic_cnt[s[left]] -= 1
                if dic_cnt[s[left]] < form_t[s[left]]:
                    current_cnt -= 1
                    tmp = s[left: right + 1]
                    min_len = tmp if len(tmp) < len(min_len) else min_len
            left += 1
        right += 1
    return min_len if min_len != s + t else ""

No.14 - Longest Common Prefix

Pair Match or Mapping

No.20 - Valid Parentheses
HashTable

No.10 - Regular Expression Matching
DP

No.13 - Roman to Integer
HashTable

No.17 - Letter Combinations of a Phone Number

No.91 - Decode Ways
DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# dp[i] means s[:i+1] can be decoded in dp[i] ways
dp = [0 for _ in range(len(s))] # max is dp[len(s)]
if s[0] != "0":
    dp[0] = 1
else:
    return 0
    
for i in range(1, len(dp)):
    if s[i] != "0":
        dp[i] += dp[i - 1]
    if 10 <= int(s[i-1:i+1]) <= 26:
        dp[i] += dp[i - 2] if i - 2 >= 0 else 1
        
return dp[-1]

No.44 - Wildcard Matching
DP

Formation

No.49 - Group Anagrams
HastTable

Valid string

No.8 String to integer

No.227 Basic Calculator II