## String and hash table (Python)

The art of deceiving Hu 2020-11-13 03:19:53
string hash table python

Catalog

character string ：

Trie Trees ：

Simple string matching algorithm ：

Related exercises ：

Hashtable ：

LRU Cache elimination algorithm ：

Related exercises ：

# character string ：

## Trie Trees ：

``````class Trie(object):
def __init__(self):
"""
"""
self.root = {}
self.end = '/'
def insert(self, word): # Insert
"""
Inserts a word into the trie.
:type word: str
:rtype: None
"""
node = self.root
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node[self.end] = None
def search(self, word):# lookup
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
node = self.root
for c in word:
if c not in node:
return False
node = node[c]
if self.end in node:
return True
else:
return False
def startsWith(self, prefix):# Prefix
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
node = self.root
for c in prefix:
if c not in node:
return False
node = node[c]
return Tru``````

## Simple string matching algorithm ：

``````# Simple matching
def matchStr(strs,substrs):
i = 0
j = 0
if not substrs:
return True
if not strs:
return False
while i<len(strs) and j<len(substrs):
print 'str: ',strs[i]
print 'substr: ',substrs[j]
if strs[i]==substrs[j]:
i += 1
j += 1
else:
i = i-j+1
j = 0
if j >= len(substrs):
return True
return False
# test
a = "asdefvgty"
b = "vgt"
print matchStr(a,b)``````

## Related exercises ：

Reverse string

Write a function , Its function is to invert the input string . Input string as character array  `char[]`  Given in the form of .

``````class Solution(object):
def reverseString(self, s):
"""
:type s: List[str]
:rtype: None Do not return anything, modify s in-place instead.
"""
l = len(s)
if l<=1:
return
for i in range(l/2):
s[i],s[l-1-i] = s[l-1-i],s[i]``````

Flip the words in the string

Given a string , Flip each word in the string one by one .

``````class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
if not s:
return ""
s_list = s.split(' ')
ret_list = [i for i in s_list if i != '']
ret_list = ret_list[::-1]
return ' '.join(ret_list)``````

String conversion integers (atoi)

First , This function discards the useless start space characters as needed , Until the first non space character is found .

When the first non empty character we find is a positive or negative sign , Then combine the symbol with as many consecutive numbers as possible on the back face , As the sign of the integer ; If the first non empty character is a number , Then combine it directly with the following consecutive numeric characters , Form an integer .

``````class Solution(object):
def myAtoi(self, str):
"""
:type str: str
:rtype: int
"""
s = str.strip()
ret =''
if len(s)<1:
return 0
if s=='-' or s=='+':# Minus sign
if len(s)<=1 or not s.isdigit():
return 0
else:
ret += s
for i in range(1,len(s)):
if s[i].isdigit():
ret += s[i]
else:
break
elif not s.isdigit():# Letter
return 0
else:# Numbers
for i in range(0,len(s)):
if s[i].isdigit():
ret += s[i]
else:
break
num = int(ret)
if num>2**31-1:
return 2**31-1
elif num<-2**31:
return -2**31
else:
return num``````

# Hashtable ：

## LRU Cache elimination algorithm ：

``````from collections import OrderedDict
class LRU():
def __init__(self,capacity = 10):
self.maxcount = capacity
self.queue = OrderedDict()
def get(self,key):
if key not in self.queue:
return -1
else:
value = self.queue.pop(key)
self.queue[key] = value
return value
def put(self,key,data):
if key in self.queue:
self.queue.pop(key)
self.queue[key] = data
else:
if len(self.queue.items()) == self.maxcount:
self.queue.popitem(last = False)
self.queue[key] = data
else:
self.queue[key] = data``````

## Related exercises ：

Sum of two numbers

Given an array of integers  `nums`  And a target value  `target`, Please find and as the target value in the array   Two   Integers , And return their array subscripts

``````class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
mydict = {}
for i in range(len(nums)):
if target-nums[i] in mydict:
return [mydict[target-nums[i]],i]
else:
mydict[nums[i]] = i``````

Happy number

Write an algorithm to determine whether a number is “ Happy number ”.

One “ Happy number ” Defined as ： For a positive integer , Replace the number with the sum of the squares of the numbers in each of its positions , Then repeat the process until the number becomes 1, It can also be an infinite loop but never change 1. If it can be 1, So this number is the happy number .

``````class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
history = []
while n>=10:
print 'n-:',n
sumnow = 0
m = 0
while n>=10:
m = n%10
n = n/10
sumnow += m*m
sumnow += n*n
n = sumnow
print 'n+:',n
return n == 1 or n == 7``````