Skip to content

Latest commit

 

History

History
115 lines (97 loc) · 4.74 KB

File metadata and controls

115 lines (97 loc) · 4.74 KB

09

String

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 code

String 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_uppercase

Sliding 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 += 1

String Basics

String Operations

Palindrome

Anagram

Sliding Window

Advanced String Problems

String-searching algorithms

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)