Summary of String.
LeetCode 344 Reverse String
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
left = 0
right = len(s)-1
while left<right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
LeetCode 541 Reverse String II
class Solution:
def reverseStr(self, s: str, k: int) -> str:
def reverse(t):
left = 0
right = len(t)-1
while left<right:
t[left], t[right] = t[right], t[left]
left += 1
right -= 1
return t
res = list(s)
for i in range(0, len(res), 2*k):
res[i:i+k] = reverse(res[i:i+k])
return ''.join(res)
JZ Offer 5
class Solution:
def replaceSpace(self, s: str) -> str:
cnt = s.count(' ')
res = list(s)
res.extend([' '] * cnt * 2)
left, right = len(s)-1, len(res)-1
while left >= 0:
if res[left] != ' ':
res[right] = res[left]
right -= 1
else:
res[right-2: right+1] = '%20'
right -= 3
left -= 1
return ''.join(res)
LeetCode 151 Reverse Words in a String
class Solution:
def trim_space(self, s):
n = len(s)
left = 0
right = n-1
while s[left] == ' ':
left += 1
while s[right] == ' ':
right -= 1
tmp = []
while left <= right:
if s[left] != ' ':
tmp.append(s[left])
elif tmp[-1] != ' ':
tmp.append(s[left]) # add inner space
left += 1
return tmp
def reverse(self, t, left, right):
while left < right:
t[left], t[right] = t[right], t[left]
left += 1
right -= 1
return None
def reverse_word(self, t):
start = 0
end = 0
n = len(t)
while start<n:
while end < n and t[end] != ' ': # determine words
end += 1
self.reverse(t, start, end-1)
start=end+1
end+=1
return None
def reverseWords(self, s: str) -> str:
l = self.trim_space(s)
self.reverse(l, 0, len(l)-1) # reverse all characters
self.reverse_word(l) # reverse back each word
return ''.join(l)
JZ Offer 58 II
class Solution:
def reverseLeftWords(self, s: str, n: int) -> str:
s = list(s)
s[:n] = list(reversed(s[:n]))
s[n:] = list(reversed(s[n:]))
s.reverse()
return ''.join(s)
class Solution:
def reverseLeftWords(self, s: str, n: int) -> str:
def reverse_fn(s, left, right):
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
s = list(s)
end = len(s)-1
reverse_fn(s, 0, n-1)
reverse_fn(s, n, end)
reverse_fn(s, 0, end)
return ''.join(s)
LeetCode 28 Implement strStr()
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
n = len(haystack)
m = len(needle)
for i in range(n-m+1):
if haystack[i:i+m] == needle:
return i
return -1
# KMP
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
n = len(haystack)
m = len(needle)
if m == 0: return 0
tab =self.prefix_table(needle)
p = -1
for i in range(n):
while p > -1 and haystack[i] != needle[p+1]:
p=tab[p]
if haystack[i] == needle[p+1]:
p += 1
if p == m-1: # p moving to the end of the tab
return i-m+1 # first index
return -1
def prefix_table(self, needle):
a = len(needle)
k = -1
tab = ['' for i in range(a)]
tab[0] = k
for i in range(1,a):
while k > -1 and needle[k+1] != needle[i]:
k = tab[k]
if needle[k+1] == needle[i]:
k += 1
tab[i] = k
return tab
LeetCode 459 Repeated Substring Pattern
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
n = len(s)
for i in range(1, n//2+1): # pattern length, cannot be longer than a half of s
if n % i == 0: # s must be a multiple of the pattern
if all(s[j] == s[j-i] for j in range(i, n)):
return True
return False
# KMP
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
if len(s) == 0:
return False
tab = self.prefix_table(s)
if tab[-1] != -1 and len(s) % (len(s) - (tab[-1] + 1)) == 0:
return True
return False
def prefix_table(self, s):
tab = [0] * len(s)
tab[0] = -1
j = -1
for i in range(1, len(s)):
while j >= 0 and s[i] != s[j+1]:
j = tab[j]
if s[i] == s[j+1]:
j += 1
tab[i] = j
return tab
LeetCode 3 Longest Substring Without Repeating Characters
Longest Substring Without Repeating Characters (Medium) [link]
Using siding window and set. We choose set because we want unique characters in the substring and we are not counting occurrences. Time complexity O(n).
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
n = len(s)
subset = set()
right = -1
ans = 0
for i in range(n):
if i != 0:
subset.remove(s[i - 1])
while right + 1 < n and s[right + 1] not in subset:
subset.add(s[right + 1])
right += 1
ans = max(ans, right - i + 1)
return ans
LeetCode 438 Find All Anagrams in a String
Find All Anagrams in a String (Medium) [link]
1] Time complexity O(nk). It exceeds the time limit because the input s string could be very long.
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
length = len(p)
res = []
for i in range(len(s)-length+1):
HashTable = [0]*26
sub = s[i:i+length]
for j in range(len(sub)):
HashTable[ord(sub[j]) - ord('a')] += 1
for q in range(len(p)):
HashTable[ord(p[q]) - ord('a')] -= 1
res.append(i)
for l in HashTable:
if l != 0:
res.remove(i)
break
return res
2] Using sliding window and dictionary.
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
len_s, len_p = len(s), len(p)
cntp = collections.Counter(p)
res = []
right = len_p
left = 0
cnt = collections.Counter(s[left:right])
if cntp == cnt:
res.append(left)
while right < len(s):
cnt[s[right]] += 1
cnt[s[left]] -= 1
if cnt[s[left]] == 0:
del cnt[s[left]]
if cntp == cnt:
res.append(left+1)
right += 1
left += 1
return res
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
np = len(p)
counterp = collections.Counter(p)
right = np-1
left = 0
counters = collections.Counter(s[left:right])
ans = []
while right < len(s):
counters[s[right]] += 1
if counters == counterp:
ans.append(left)
counters[s[left]] -= 1
if counters[s[left]] == 0:
del counters[s[left]]
left += 1
right += 1
return ans
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
len_s, len_p = len(s), len(p)
res = []
tab_s, tab_p = [0] * 26, [0] * 26
if len_s < len_p:
return res
for i in range(len_p):
tab_s[ord(s[i]) - ord('a')] += 1
tab_p[ord(p[i]) - ord('a')] += 1
if tab_s == tab_p:
res.append(0)
for i in range(len_p, len_s):
tab_s[ord(s[i-len_p]) - ord('a')] -= 1
tab_s[ord(s[i]) - ord('a')] += 1
if tab_s == tab_p:
res.append(i-len_p+1)
return res
LeetCode 567 Permutation in String
Permutation in String (Medium) [link]
Use sliding window of length |s1| to move on s2, and dictionary to determine the occurrence of characters. We choose dictionary here because we need the occurrence to be exactly the same.
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
counter1 = collections.Counter(s1)
n1 = len(s1)
right = n1 - 1
left = 0
counter2 = collections.Counter(s2[left:right])
while right < len(s2):
counter2[s2[right]] += 1
if counter1 == counter2:
return True
counter2[s2[left]] -= 1
if counter2[s2[left]] == 0:
del counter2[s2[left]]
left += 1
right += 1
return False
