# Find Words

## # Solution

Let be length of str and length of dict.

We need two pointers, i in str and j in dict.

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.

### # Matrix

Go from back to front, nextpos[i][j] is the next position of char j after str[i]. If str[i]==j, then nextpos[i][j] = i.

Complexity:

• time:
• space:
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

Last Updated: 5/13/2020, 7:39:18 AM