數據結構3.1

Problem: Implement an algorithm to determine if a string has all unique characters判斷一個字元串是否每個字元都不重複Test Cases* None -> False* -> True* foo -> False* bar -> Truecodeclass UniqueChars(object): def has_unique_chars(self, string): if string==None: return False #方法一 return len(set(string))==len(string) Time: O(n) Space: Additional O(n) #方法二# hmap=set()# for str in string:# if str in hmap:# return False# else:# hmap.add(str) # return True Time: O(n) Space: Additional O(n) #方法三 for str in string: if string.count(str)>1: return False return True

Problem: Determine if a string is a permutation of another string.判斷一個字元串是否是另一個字元串的置換Test Cases* One or more None inputs -> False* One or more empty strings -> False* Nib, bin -> False* act, cat -> True* a ct, ca t -> Truefrom collections import defaultdictclass Permutations(object): def is_permutation(self, str1, str2): if str1==None or str2==None: return False if len(str1) != len(str2): return False #方法一# set1=set(str1)# set2=set(str2)# if set1==set2:# return True# else:# return False #方法二# return sorted(str1)==sorted(str2) #方法三# dict1=defaultdict(int)# dict2=defaultdict(int) # for i in str1:# dict1[i]+=1# for j in str2:# dict2[j]+=1# return dict1==dict2 #方法四 for i in str1: if i not in str2: return False return True

Problem: Determine if a string s1 is a rotation of another string s2, by calling (only once) a function is_substring.判斷字元串s1 是否是 s2的循環(旋轉)字元串,要求調用一次is_substringTest CasesAny strings that differ in size -> FalseNone, foo -> False (any None results in False) , foo -> False , -> Truefoobarbaz, barbazfoo -> Trueclass Rotation(object): def is_substring(self, s1, s2): # TODO: Implement me return s1 in s2 def is_rotation(self, s1, s2): # TODO: Implement me # Call is_substring only once if s1==None or s2==None: return False if len(s1)!=len(s2): return False return self.is_substring(s1,s2+s2)

推薦閱讀：