We need two pointers,
Brute force solution is to compare 2 pointers until
i gets to end of
str. This is not time efficient especially when
str is long.
So we need to preprocess w/ data structures such matrix or HashMap.
Go from back to front,
nextpos[i][j] is the next position of char
nextpos[i][j] = i.
def findWords(self, str, dict): if not str or not dict: return  n, res = len(str),  nextpos = [[n]*26 for _ in range(n+1)] # preprocessing for i in reversed(range(n)): for j in range(26): nextpos[i][j] = nextpos[i+1][j] if ord(str[i])-ord('a')==j: nextpos[i][j] = i # 2 pointers comparision for word in dict: # i points in str, j points in dict i, j, m = 0, 0, len(word) while i<n and j<m: i = nextpos[i][ord(word[j])-ord('a')] if i==n: # word not found in str break i += 1 j += 1 if j==m: res.append(word) return res