# 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:

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

# Solution 1: HashTable

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

Space complexity: O(sum(l))

## Solution2: Trie

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

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

# Problem

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"


Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.


Note:

All given inputs are in lowercase letters a-z.

# Solution: Brute Force

Time complexity: O(mk), where k the length of common prefix.

Space complexity: O(k)

## Java

Time complexity: (mk + k^2)

## Python3

Problem:

Given many wordswords[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:

Note:

1. words has length in range [1, 15000].
2. For each test case, up to words.length queries WordFilter.f may be made.
3. words[i] has length in range [1, 10].
4. prefix, suffix have lengths in range [0, 10].
5. 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)

Version #2

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)

Related Problems:

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:

Example 2:

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++

Trie + Sorting

Trie + No sorting

Problem:

Implement a trie with insertsearch, and startsWith methods.

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

Idea:

Tree/children array

Solution:

C++ / Array

C++ / hashmap

Java

Python 1:

Python 2: