In this question if I consider the length of the array words1 as n and words2 as m, then for my first loop the time complexity would be m*k [where k is the average length of the string in words2], and for the second nested loop, n*26 [as the keys in the hashmap can not be greater than 26]. The total time complexity would be O(n+(m*k)) and roughly O(n+m). I want to clarify if I am calculating the time complexity right?
def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]: ans = [] hmap = {} for i in words2: for j in i: if j in hmap.keys(): hmap[j] = max(hmap[j], i.count(j)) else: hmap[j] = i.count(j) for j in words1: flag = True for k in hmap.keys(): if hmap[k] > j.count(k): flag = False break if flag: ans.append(j) return ans
submitted by /u/Nyctophilic_enigma
[link] [comments]
r/learnpython In this question if I consider the length of the array words1 as n and words2 as m, then for my first loop the time complexity would be m*k [where k is the average length of the string in words2], and for the second nested loop, n*26 [as the keys in the hashmap can not be greater than 26]. The total time complexity would be O(n+(m*k)) and roughly O(n+m). I want to clarify if I am calculating the time complexity right? def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]: ans = [] hmap = {} for i in words2: for j in i: if j in hmap.keys(): hmap[j] = max(hmap[j], i.count(j)) else: hmap[j] = i.count(j) for j in words1: flag = True for k in hmap.keys(): if hmap[k] > j.count(k): flag = False break if flag: ans.append(j) return ans submitted by /u/Nyctophilic_enigma [link] [comments]
In this question if I consider the length of the array words1 as n and words2 as m, then for my first loop the time complexity would be m*k [where k is the average length of the string in words2], and for the second nested loop, n*26 [as the keys in the hashmap can not be greater than 26]. The total time complexity would be O(n+(m*k)) and roughly O(n+m). I want to clarify if I am calculating the time complexity right?
def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]: ans = [] hmap = {} for i in words2: for j in i: if j in hmap.keys(): hmap[j] = max(hmap[j], i.count(j)) else: hmap[j] = i.count(j) for j in words1: flag = True for k in hmap.keys(): if hmap[k] > j.count(k): flag = False break if flag: ans.append(j) return ans
submitted by /u/Nyctophilic_enigma
[link] [comments]