Find Words

problem at: https://www.lintcode.com/problem/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