Skip to content

745. Prefix and Suffix Search 👍

Approach 1: HashTable

  • Time: $O(|\texttt{words}||\texttt{word[i]}|^3) + O(q|\texttt{word[i]}|)$
  • Space: $O(|\texttt{words}||\texttt{word[i]}|^3)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class WordFilter {
 public:
  WordFilter(vector<string>& words) {
    for (int i = 0; i < words.size(); ++i) {
      const string& word = words[i];
      vector<string> prefixes;
      vector<string> suffixes;
      for (int j = 0; j <= word.length(); ++j) {
        const string prefix = word.substr(0, j);
        const string suffix = word.substr(j);
        prefixes.push_back(prefix);
        suffixes.push_back(suffix);
      }
      for (const string& prefix : prefixes)
        for (const string& suffix : suffixes)
          keyToIndex[prefix + '_' + suffix] = i;
    }
  }

  int f(string prefix, string suffix) {
    const string key = prefix + '_' + suffix;
    if (const auto it = keyToIndex.find(key); it != keyToIndex.cend())
      return it->second;
    return -1;
  }

 private:
  unordered_map<string, int> keyToIndex;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class WordFilter {
  public WordFilter(String[] words) {
    for (int i = 0; i < words.length; ++i) {
      final String word = words[i];
      List<String> prefixes = new ArrayList<>();
      List<String> suffixes = new ArrayList<>();
      for (int j = 0; j <= word.length(); ++j) {
        final String prefix = word.substring(0, j);
        final String suffix = word.substring(j);
        prefixes.add(prefix);
        suffixes.add(suffix);
      }
      for (final String prefix : prefixes)
        for (final String suffix : suffixes)
          keyToIndex.put(prefix + '_' + suffix, i);
    }
  }

  public int f(String prefix, String suffix) {
    final String key = prefix + '_' + suffix;
    if (keyToIndex.containsKey(key))
      return keyToIndex.get(key);
    return -1;
  }

  private Map<String, Integer> keyToIndex = new HashMap<>();
}

Approach 2: Trie

  • Time: $O(|\texttt{words}||\texttt{word[i]}|^2) + O(q|\texttt{word[i]}|)$
  • Space: $O(|\texttt{words}||\texttt{word[i]}|^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
struct TrieNode {
  vector<shared_ptr<TrieNode>> children;
  int weight = -1;
  TrieNode() : children(27) {}
};

class Trie {
 public:
  void insert(const string& word, int weight) {
    shared_ptr<TrieNode> node = root;
    for (const char c : word) {
      const int i = c - 'a';
      if (node->children[i] == nullptr)
        node->children[i] = make_shared<TrieNode>();
      node = node->children[i];
      node->weight = weight;
    }
  }

  int startsWith(const string& word) {
    shared_ptr<TrieNode> node = root;
    for (const char c : word) {
      const int i = c - 'a';
      if (node->children[i] == nullptr)
        return -1;
      node = node->children[i];
    }
    return node->weight;
  }

 private:
  shared_ptr<TrieNode> root = make_shared<TrieNode>();
};

class WordFilter {
 public:
  WordFilter(vector<string>& words) {
    for (int i = 0; i < words.size(); ++i)
      for (int j = 0; j <= words[i].length(); ++j)
        trie.insert(words[i].substr(j) + '{' + words[i], i);
  }

  int f(string prefix, string suffix) {
    return trie.startsWith(suffix + '{' + prefix);
  }

 private:
  Trie trie;
};