String Operations
s.strip([chars]) # return a copy of the string with the leading and trailing characters removed.
s.startswith(prefix) # return True if string starts with the prefix, False otherwise.
s.endswith(prefix) # return True if string starts with the prefix, False otherwise.
s.slipt(delimiter) # return a list of the words of the string s.
s.lower() # return a copy of the string with all the lowercase characters
s.upper() # return a copy of the string with all the uppercase characters
ord(c) # the unicode code representation of the char
ord(c) - ord('a') # the position of the char in 26 letters
chr(i) # string representation of the char unicode codeString Constants
import string
string.digits # the string '0123456789'
string.hexdigits # the string '0123456789abcdefABCDEF'
string.octdigits # the string '01234567'
string.ascii_lowercase # the uppercase letters 'abcdefghijklmnopqrstuvwxyz'
string.ascii_letters # The lowercase letters 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
string.letters # The concatenation of the ascii_lowercase and ascii_uppercaseSliding Window Template
from collections import Counter
def slidingWindow(s, t):
window = Counter()
target = Counter(t)
valid = 0
left = right = 0
while right < len(s):
# c is the element to be inserted into the window
c = s[right]
# if we insert it, is the window still valid?
if c in target:
window[c] += 1
if window[c] == target[c]:
valid += 1
# expand the current window
right += 1
print(s[left: right])
# when we found a valid window
while right - left >= len(t):
# check the answer or update the result
if valid == len(target):
...
# d is the element to be removed from the window
d = s[left]
# if we remove it, is the window still valid?
if d in target:
if window[d] == target[d]:
valid -= 1
window[d] -= 1
# shrink the current window
left += 1String Basics
- 709. To Lower Case
- 58. Length of Last Word
- 771. Jewels and Stones
- 387. First Unique Character in a String
- 8. String to Integer (atoi)
String Operations
- 14. Longest Common Prefix
- 344. Reverse String
- 541. Reverse String II
- 151. Reverse Words in a String
- 557. Reverse Words in a String III
- 917. Reverse Only Letters
Palindrome
Anagram
Sliding Window
- 3. Longest Substring Without Repeating Characters
- 76. Minimum Window Substring
- 438. Find All Anagrams in a String
- 567. Permutation in String
Advanced String Problems
| algorithm | Preprocessing Time | Matching Time | Space |
|---|---|---|---|
| Naive | None | O(mn) | None |
| Rabin-Karp | O(m) | O(n+m) | O(1) |
| KMP | O(m) | O(n) | O(m) |
| Boyer-Moore | O(m+k) | O(mn) | O(k) |