Posts tagged as “trie”

花花酱 LeetCode 648. Replace Words

By zxi on November 8, 2018

Problem

https://leetcode.com/problems/replace-words/description/

In English, we have a concept called root, which can be followed by some other words to form another longer word – let’s call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Note:

The input will only have lower-case letters.
1 <= dict words number <= 1000
1 <= sentence words number <= 1000
1 <= root length <= 100
1 <= sentence words length <= 1000

Solution 1: HashTable

Time complexity: O(sum(w^2))

Space complexity: O(sum(l))

// Author: Huahua, Running time: 84 ms

class Solution {

public:

string replaceWords(vector<string>& dict, string sentence) {

unordered_set<string> d(begin(dict), end(dict));

sentence.push_back(' ');

string output;

string word;

bool found = false;

for (char c : sentence) {

if (c == ' ') {

if (!output.empty()) output += ' ';

output += word;

word = "";

found = false;

continue;

}

if (found) continue;

word += c;

if (d.count(word)) {

found = true;

}

return output;

}

};

Solution2: Trie

Time complexity: O(sum(l) + n)

Space complexity: O(sum(l) * 26)

// Author: Huahua, running time: 48 ms

class TrieNode {

public:

TrieNode(): children(26), is_word(false) {}

~TrieNode() {

for (int i = 0; i < 26; ++i)

if (children[i]) {

delete children[i];

children[i] = nullptr;

}

vector<TrieNode*> children;

bool is_word;

};

class Solution {

public:

string replaceWords(vector<string>& dict, string sentence) {

TrieNode root;

for (const string& word : dict) {

TrieNode* cur = &root;

for (char c : word) {

if (!cur->children[c - 'a']) cur->children[c - 'a'] = new TrieNode();

cur = cur->children[c - 'a'];

}

cur->is_word = true;

}

string ans;

stringstream ss(sentence);

string word;

while (ss >> word) {

TrieNode* cur = &root;

bool found = false;

int len = 0;

for (char c : word) {

cur = cur->children[c - 'a'];

if (!cur) break;

++len;

if (cur->is_word) {

found = true;

break;

}

if (!ans.empty()) ans += ' ';

ans += found ? word.substr(0, len) : word;

}

return ans;

}

};

花花酱 LeetCode 745. Prefix and Suffix Search

By zxi on December 11, 2017

Link: https://leetcode.com/problems/prefix-and-suffix-search/description/

Problem:

Given many words, words[i] has weight i.

Design a class WordFilter that supports one function, WordFilter.f(String prefix, String suffix). It will return the word with given prefix and suffix with maximum weight. If no word exists, return -1.

Examples:

Input:

WordFilter(["apple"])

WordFilter.f("a", "e") // returns 0

WordFilter.f("b", "") // returns -1

Note:

words has length in range [1, 15000].
For each test case, up to words.length queries WordFilter.f may be made.
words[i] has length in range [1, 10].
prefix, suffix have lengths in range [0, 10].
words[i] and prefix, suffix queries consist of lowercase letters only.

Idea:

Construct all possible filters

Solution1:

C++

Time complexity: O(NL^3 + QL) where N is the number of words, L is the max length of the word, Q is the number of queries.

Space complexity: O(NL^3)

// Author: Huahua

// Runtime: 482 ms

class WordFilter {

public:

WordFilter(const vector<string>& words) {

int index = 0;

for (const string& word : words) {

int n = word.length();

string prefix;

for (int i = 0; i <= n; ++i) {

if (i > 0) prefix += word[i - 1];

string suffix;

for (int j = n; j >= 0; --j) {

if (j != n) suffix = word[j] + suffix;

const string key = prefix + "_" + suffix;

filters_[key] = index;

}

++index;

}

int f(string prefix, string suffix) {

const string key = prefix + "_" + suffix;

auto it = filters_.find(key);

if (it != filters_.end()) return it->second;

return -1;

}

private:

unordered_map<string, int> filters_;

};

Version #2

// Author: Huahua

// Runtime: 499 ms

class WordFilter {

public:

WordFilter(const vector<string>& words) {

int index = 0;

for (const string& word : words) {

int n = word.length();

vector<string> prefixes(n + 1, "");

vector<string> suffixes(n + 1, "");

for (int i = 0; i < n; ++i) {

prefixes[i + 1] = prefixes[i] + word[i];

suffixes[i + 1] = word[n - i - 1] + suffixes[i];

}

for (const string& prefix : prefixes)

for (const string& suffix : suffixes)

filters_[prefix + "_" + suffix] = index;

++index;

}

int f(string prefix, string suffix) {

const string key = prefix + "_" + suffix;

auto it = filters_.find(key);

if (it != filters_.end()) return it->second;

return -1;

}

private:

unordered_map<string, int> filters_;

};

Solution 2:

C++ / Trie

Time complexity: O(NL^2 + QL) where N is the number of words, L is the max length of the word, Q is the number of queries.

Space complexity: O(NL^2)

// Author: Huahua

// Runtime: 572 ms

class Trie {

public:

/** Initialize your data structure here. */

Trie(): root_(new TrieNode()) {}

/** Inserts a word into the trie. */

void insert(const string& word, int index) {

TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children[c - 'a'])

p->children[c - 'a'] = new TrieNode();

p = p->children[c - 'a'];

// Update index

p->index = index;

}

p->is_word = true;

}

/** Returns the index of word that has the prefix. */

int startsWith(const string& prefix) const {

auto node = find(prefix);

if (!node) return -1;

return node->index;

}

private:

struct TrieNode {

TrieNode():index(-1), is_word(false), children(27, nullptr){}

~TrieNode() {

for (TrieNode* child : children)

if (child) delete child;

}

int index;

int is_word;

vector<TrieNode*> children;

};

const TrieNode* find(const string& prefix) const {

const TrieNode* p = root_.get();

for (const char c : prefix) {

p = p->children[c - 'a'];

if (p == nullptr) break;

}

return p;

}

std::unique_ptr<TrieNode> root_;

};

class WordFilter {

public:

WordFilter(vector<string> words) {

for (int i = 0; i < words.size(); ++i) {

const string& w = words[i];

string key = "{" + w;

trie_.insert(key, i);

for (int j = 0; j < w.size(); ++j) {

key = w[w.size() - j - 1] + key;

trie_.insert(key, i);

}

int f(string prefix, string suffix) {

return trie_.startsWith(suffix + "{" + prefix);

}

private:

Trie trie_;

};

Related Problems:

花花酱 LeetCode 720. Longest Word in Dictionary

By zxi on November 16, 2017

Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

If there is no answer, return the empty string.

Example 1:

Input:

words = ["w","wo","wor","worl", "world"]

Output: "world"

Explanation:

The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Example 2:

Input:

words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]

Output: "apple"

Explanation:

Both "apply" and "apple" can be built from other words in the dictionary.

However, "apple" is lexicographically smaller than "apply".

Note:

All the strings in the input will only contain lowercase letters.
The length of words will be in the range [1, 1000].
The length of words[i] will be in the range [1, 30].

Idea:

Brute force

Trie

Solution:

C++

// Author: Huahua

// Runtime: 39 ms (better than 97.85%)

class Solution {

public:

string longestWord(vector<string>& words) {

string best;

unordered_set<string> dict(words.begin(), words.end());

for (const string& word : words) {

if (word.length() < best.length()

|| (word.length() == best.length() && word > best))

continue;

string prefix;

bool valid = true;

for (int i = 0; i < word.length() - 1 && valid; ++i) {

prefix += word[i];

if (!dict.count(prefix)) valid = false;

}

if (valid) best = word;

}

return best;

}

};

// Author: Huahua

// Runtime: 46 ms

class Solution {

public:

string longestWord(vector<string>& words) {

// Sort by length DESC, if there is a tie, sort by lexcial order.

std::sort(words.begin(), words.end(),

[](const string& w1, const string& w2){

if (w1.length() != w2.length())

return w1.length() > w2.length();

return w1 < w2;

});

unordered_set<string> dict(words.begin(), words.end());

for (const string& word : words) {

string prefix;

bool valid = true;

for (int i = 0; i < word.length() - 1 && valid; ++i) {

prefix += word[i];

if (!dict.count(prefix)) valid = false;

}

if (valid) return word;

}

return "";

}

};

Trie + Sorting

// Author: Huahua

// Runtime: 49 ms

class Trie {

public:

Trie(): root_(new TrieNode()) {}

void insert(const string& word) {

TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children[c - 'a'])

p->children[c - 'a'] = new TrieNode();

p = p->children[c - 'a'];

}

p->is_word = true;

}

bool hasAllPrefixes(const string& word) {

const TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children[c - 'a']) return false;

p = p->children[c - 'a'];

if (!p->is_word) return false;

}

return true;

}

private:

struct TrieNode {

TrieNode():is_word(false), children(26, nullptr){}

~TrieNode() {

for (auto node : children)

delete node;

}

bool is_word;

vector<TrieNode*> children;

};

std::unique_ptr<TrieNode> root_;

};

class Solution {

public:

string longestWord(vector<string>& words) {

std::sort(words.begin(), words.end(),

[](const string& w1, const string& w2){

if (w1.length() != w2.length())

return w1.length() > w2.length();

return w1 < w2;

});

Trie trie;

for (const string& word : words)

trie.insert(word);

for (const string& word : words)

if (trie.hasAllPrefixes(word)) return word;

return "";

}

};

Trie + No sorting

// Author: Huahua

// Runtime: 56 ms

class Trie {

public:

Trie(): root_(new TrieNode()) {}

void insert(const string& word) {

TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children[c - 'a'])

p->children[c - 'a'] = new TrieNode();

p = p->children[c - 'a'];

}

p->is_word = true;

}

bool hasAllPrefixes(const string& word) {

const TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children[c - 'a']) return false;

p = p->children[c - 'a'];

if (!p->is_word) return false;

}

return true;

}

private:

struct TrieNode {

TrieNode():is_word(false), children(26, nullptr){}

~TrieNode() {

for (auto node : children)

delete node;

}

bool is_word;

vector<TrieNode*> children;

};

std::unique_ptr<TrieNode> root_;

};

class Solution {

public:

string longestWord(vector<string>& words) {

Trie trie;

for (const string& word : words)

trie.insert(word);

string best;

for (const string& word : words) {

if (word.length() < best.length()

|| (word.length() == best.length() && word > best))

continue;

if (trie.hasAllPrefixes(word))

best = word;

}

return best;

}

};

花花酱 LeetCode 208. Implement Trie (Prefix Tree)

By zxi on September 27, 2017

Problem:

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

Idea:

Tree/children array

Solution:

C++ / Array

// Author: Huahua

// Running time: 99 ms

class Trie {

public:

/** Initialize your data structure here. */

Trie(): root_(new TrieNode()) {}

/** Inserts a word into the trie. */

void insert(const string& word) {

TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children[c - 'a'])

p->children[c - 'a'] = new TrieNode();

p = p->children[c - 'a'];

}

p->is_word = true;

}

/** Returns if the word is in the trie. */

bool search(const string& word) const {

const TrieNode* p = find(word);

return p && p->is_word;

}

/** Returns if there is any word in the trie that starts with the given prefix. */

bool startsWith(const string& prefix) const {

return find(prefix) != nullptr;

}

private:

struct TrieNode {

TrieNode():is_word(false), children(26, nullptr){}

~TrieNode() {

for (TrieNode* child : children)

if (child) delete child;

}

bool is_word;

vector<TrieNode*> children;

};

const TrieNode* find(const string& prefix) const {

const TrieNode* p = root_.get();

for (const char c : prefix) {

p = p->children[c - 'a'];

if (p == nullptr) break;

}

return p;

}

std::unique_ptr<TrieNode> root_;

};

C++ / hashmap

// Author: Huahua

// Running time: 98 ms

class Trie {

public:

/** Initialize your data structure here. */

Trie(): root_(new TrieNode()) {}

/** Inserts a word into the trie. */

void insert(const string& word) {

TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children.count(c))

p->children[c] = new TrieNode();

p = p->children[c];

}

p->is_word = true;

}

/** Returns if the word is in the trie. */

bool search(const string& word) const {

const TrieNode* p = find(word);

return p && p->is_word;

}

/** Returns if there is any word in the trie that starts with the given prefix. */

bool startsWith(const string& prefix) const {

return find(prefix) != nullptr;

}

private:

struct TrieNode {

TrieNode():is_word(false){}

~TrieNode() {

for (auto& kv : children)

if (kv.second) delete kv.second;

}

bool is_word;

unordered_map<char, TrieNode*> children;

};

const TrieNode* find(const string& prefix) const {

const TrieNode* p = root_.get();

for (const char c : prefix) {

if (!p->children.count(c)) return nullptr;

p = p->children.at(c);

}

return p;

}

std::unique_ptr<TrieNode> root_;

};

Java

// Author: Huahua

// Running time: 184 ms

class Trie {

class TrieNode {

public TrieNode() {

children = new TrieNode[26];

is_word = false;

}

public boolean is_word;

public TrieNode[] children;

}

private TrieNode root;

/** Initialize your data structure here. */

public Trie() {

root = new TrieNode();

}

/** Inserts a word into the trie. */

public void insert(String word) {

TrieNode p = root;

for (int i = 0; i < word.length(); i++) {

int index = (int)(word.charAt(i) - 'a');

if (p.children[index] == null)

p.children[index] = new TrieNode();

p = p.children[index];

}

p.is_word = true;

}

/** Returns if the word is in the trie. */

public boolean search(String word) {

TrieNode node = find(word);

return node != null && node.is_word;

}

/** Returns if there is any word in the trie that starts with the given prefix. */

public boolean startsWith(String prefix) {

TrieNode node = find(prefix);

return node != null;

}

private TrieNode find(String prefix) {

TrieNode p = root;

for(int i = 0; i < prefix.length(); i++) {

int index = (int)(prefix.charAt(i) - 'a');

if (p.children[index] == null) return null;

p = p.children[index];

}

return p;

}

Python 1:

"""

Author: Huahua

Running time: 469 ms

"""

class Trie(object):

class TrieNode(object):

def __init__(self):

self.is_word = False

self.children = [None] * 26

def __init__(self):

self.root = Trie.TrieNode()

def insert(self, word):

p = self.root

for c in word:

index = ord(c) - ord('a')

if not p.children[index]:

p.children[index] = Trie.TrieNode()

p = p.children[index]

p.is_word = True

def search(self, word):

node = self.find(word)

return node is not None and node.is_word

def startsWith(self, prefix):

return self.find(prefix) is not None

def find(self, prefix):

p = self.root

for c in prefix:

index = ord(c) - ord('a')

if not p.children[index]: return None

p = p.children[index]

return p

Python 2:

"""

Author: Huahua

Running time: 212 ms

"""

class Trie(object):

def __init__(self):

self.root = {}

def insert(self, word):

p = self.root

for c in word:

if c not in p:

p[c] = {}

p = p[c]

p['#'] = True

def search(self, word):

node = self.find(word)

return node is not None and '#' in node

def startsWith(self, prefix):

return self.find(prefix) is not None

def find(self, prefix):

p = self.root

for c in prefix:

if c not in p: return None

p = p[c]

return p

花花酱 LeetCode 677. Map Sum Pairs

By zxi on September 18, 2017

https://leetcode.com/problems/map-sum-pairs/description/

Problem:

Implement a MapSum class with insert, and sum methods.

For the method insert, you’ll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.

For the method sum, you’ll be given a string representing the prefix, and you need to return the sum of all the pairs’ value whose key starts with the prefix.

Example 1:

Input: insert("apple", 3), Output: Null

Input: sum("ap"), Output: 3

Input: insert("app", 2), Output: Null

Input: sum("ap"), Output: 5

Idea:

Prefix tree

Solution 1

// Author: Huahua

// Running time: 3 ms

class MapSum {

public:

/** Initialize your data structure here. */

MapSum() {}

void insert(const string& key, int val) {

int inc = val;

if (vals_.count(key)) {

inc -= vals_[key];

}

vals_[key] = val;

for (int i = 1; i <= key.length(); ++i)

sums_[key.substr(0,i)] += inc;

}

int sum(const string& prefix) {

return sums_[prefix];

}

private:

unordered_map<string, int> vals_;

unordered_map<string, int> sums_;

};

Solution 2:

class MapSum {

public:

/** Initialize your data structure here. */

MapSum() {}

void insert(string key, int val) {

int inc = val - vals_[key];

Trie* p = &root;

for (const char c : key) {

if (!p->children[c])

p->children[c] = new Trie();

p->children[c]->sum += inc;

p = p->children[c];

}

vals_[key] = val;

}

int sum(string prefix) {

Trie* p = &root;

for (const char c : prefix) {

if (!p->children[c]) return 0;

p = p->children[c];

}

return p->sum;

}

private:

struct Trie {

Trie():children(128, nullptr), sum(0){}

~Trie() {

for (auto child : children)

if (child) delete child;

children.clear();

}

vector<Trie*> children;

int sum;

};

Trie root; // dummy root

unordered_map<string, int> vals_; // key -> val

};

with std::unique_ptr

// Author: Huahua

// Running time: 5 ms

class MapSum {

public:

/** Initialize your data structure here. */

MapSum(): root_(new Trie()) {}

void insert(string key, int val) {

int inc = val - vals_[key];

Trie* p = root_.get();

for (const char c : key) {

if (!p->children[c])

p->children[c] = new Trie();

p->children[c]->sum += inc;

p = p->children[c];

}

vals_[key] = val;

}

int sum(string prefix) {

Trie* p = root_.get();

for (const char c : prefix) {

if (!p->children[c]) return 0;

p = p->children[c];

}

return p->sum;

}

private:

struct Trie {

Trie():children(128, nullptr), sum(0){}

~Trie() {

for (auto child : children)

if (child) {

delete child;

child = nullptr;

}

children.clear();

}

vector<Trie*> children;

int sum;

};

std::unique_ptr<Trie> root_;

unordered_map<string, int> vals_; // key -> val

};