Spaces:
Sleeping
Sleeping
File size: 5,368 Bytes
4a3f117 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 | STRING ALGORITHMS
=================
Strings are sequences of characters. Most string operations in Python run in O(n).
--- Basic String Operations ---
s = "hello world"
print(len(s)) # 11
print(s.upper()) # HELLO WORLD
print(s.lower()) # hello world
print(s.split()) # ['hello', 'world']
print(s.replace("world", "Python")) # hello Python
print(s.startswith("hello")) # True
print(s.endswith("world")) # True
print(s.find("world")) # 6 (index)
print(s.count("l")) # 3
print(s[::-1]) # dlrow olleh (reverse)
print("".join(reversed(s))) # same as above
--- Reverse Words in a Sentence ---
def reverse_words(sentence):
return ' '.join(sentence.split()[::-1])
print(reverse_words("Hello World Python")) # Python World Hello
--- Check Palindrome ---
def is_palindrome(s):
s = ''.join(c.lower() for c in s if c.isalnum())
return s == s[::-1]
print(is_palindrome("A man a plan a canal Panama")) # True
print(is_palindrome("race a car")) # False
--- Anagram Check ---
Two strings are anagrams if they have same characters with same frequency.
from collections import Counter
def is_anagram(s, t):
return Counter(s) == Counter(t)
print(is_anagram("listen", "silent")) # True
print(is_anagram("hello", "world")) # False
--- Count Character Frequency ---
def char_frequency(s):
freq = {}
for ch in s:
freq[ch] = freq.get(ch, 0) + 1
return freq
print(char_frequency("abracadabra"))
# {'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}
--- KMP String Matching ---
Find all occurrences of pattern in text.
Time: O(n + m). Space: O(m). Efficient, no unnecessary comparisons.
def kmp_search(text, pattern):
n, m = len(text), len(pattern)
if m == 0:
return [0]
# Build failure function
fail = [0] * m
j = 0
for i in range(1, m):
while j > 0 and pattern[i] != pattern[j]:
j = fail[j - 1]
if pattern[i] == pattern[j]:
j += 1
fail[i] = j
# Search
matches = []
j = 0
for i in range(n):
while j > 0 and text[i] != pattern[j]:
j = fail[j - 1]
if text[i] == pattern[j]:
j += 1
if j == m:
matches.append(i - m + 1)
j = fail[j - 1]
return matches
print(kmp_search("aabaacaadaabaaba", "aaba")) # [0, 9, 12]
--- Rabin-Karp Rolling Hash ---
Find pattern in text using hashing. Avg O(n+m), worst O(nm).
def rabin_karp(text, pattern):
n, m = len(text), len(pattern)
BASE, MOD = 256, 101
pat_hash = text_hash = 0
h = pow(BASE, m - 1, MOD)
matches = []
for i in range(m):
pat_hash = (BASE * pat_hash + ord(pattern[i])) % MOD
text_hash = (BASE * text_hash + ord(text[i])) % MOD
for i in range(n - m + 1):
if pat_hash == text_hash:
if text[i:i+m] == pattern: # verify
matches.append(i)
if i < n - m:
text_hash = (BASE*(text_hash - ord(text[i])*h) + ord(text[i+m])) % MOD
if text_hash < 0:
text_hash += MOD
return matches
print(rabin_karp("GEEKS FOR GEEKS", "GEEKS")) # [0, 10]
--- Longest Common Prefix ---
def longest_common_prefix(strs):
if not strs:
return ""
prefix = strs[0]
for s in strs[1:]:
while not s.startswith(prefix):
prefix = prefix[:-1]
if not prefix:
return ""
return prefix
print(longest_common_prefix(["flower","flow","flight"])) # "fl"
print(longest_common_prefix(["dog","racecar","car"])) # ""
--- Valid Parentheses ---
def is_valid_parentheses(s):
stack = []
pairs = {')':'(', '}':'{', ']':'['}
for ch in s:
if ch in '({[':
stack.append(ch)
elif ch in ')}]':
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
return not stack
print(is_valid_parentheses("()[]{}")) # True
print(is_valid_parentheses("([)]")) # False
--- Roman to Integer ---
def roman_to_int(s):
values = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
result = 0
for i in range(len(s)):
if i + 1 < len(s) and values[s[i]] < values[s[i+1]]:
result -= values[s[i]]
else:
result += values[s[i]]
return result
print(roman_to_int("III")) # 3
print(roman_to_int("LVIII")) # 58
print(roman_to_int("MCMXCIV"))# 1994
--- String Compression ---
Compress "aabcccdddd" to "a2b1c3d4".
def compress(s):
result = []
i = 0
while i < len(s):
ch = s[i]
count = 0
while i < len(s) and s[i] == ch:
count += 1
i += 1
result.append(ch + str(count))
compressed = ''.join(result)
return compressed if len(compressed) < len(s) else s
print(compress("aabcccdddd")) # a2b1c3d4
print(compress("abcd")) # abcd (no gain)
--- Zigzag String Conversion ---
Convert string to zigzag pattern across rows.
def convert_zigzag(s, numRows):
if numRows == 1 or numRows >= len(s):
return s
rows = [''] * numRows
row, step = 0, 1
for ch in s:
rows[row] += ch
if row == 0: step = 1
if row == numRows - 1: step = -1
row += step
return ''.join(rows)
print(convert_zigzag("PAYPALISHIRING", 3)) # PAHNAPLSIIGYIR
|