https://leetcode.com/problems/longest-word-in-dictionary-through-deleting
https://www.careercup.com/question?id=5757216146587648
https://techdevguide.withgoogle.com/paths/foundational/find-longest-word-in-dictionary-that-subsequence-of-given-string/#!
If you know how to check for subsequences, and are trying to optimize: Can you preprocess
How would you approach the question if you assumed that
Would your approach change if the size of the searched-in string was much larger than the size of the dictionary?
Consider the trade-offs among different data structures for representing preprocessed data. What kind of preprocessing would be accommodated by a tree? A dictionary? A tree or dictionary of … and so on?
X.
http://www.cnblogs.com/grandyang/p/6523344.html
https://discuss.leetcode.com/topic/80799/short-java-solutions-sorting-dictionary-and-without-sorting
https://leetcode.com/articles/longest-word-in-dictionary-through-deletion/
X. DFS
Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.
Example 1:
Input: s = "abpcplea", d = ["ale","apple","monkey","plea"] Output: "apple"
Example 2:
Input: s = "abpcplea", d = ["a","b","c"] Output: "a"
Note:
- All the strings in the input will only contain lower-case letters.
- The size of the dictionary won't exceed 1,000.
- The length of all the strings in the input won't exceed 1,000.
https://www.careercup.com/question?id=5757216146587648
https://techdevguide.withgoogle.com/paths/foundational/find-longest-word-in-dictionary-that-subsequence-of-given-string/#!
If you know how to check for subsequences, and are trying to optimize: Can you preprocess
S in some way to make checking dictionary words against it very efficient?How would you approach the question if you assumed that
W*N is a lot larger than L, and that more memory can be used to speed things up. For example, what if you preprocessed D, not SWould your approach change if the size of the searched-in string was much larger than the size of the dictionary?
Consider the trade-offs among different data structures for representing preprocessed data. What kind of preprocessing would be accommodated by a tree? A dictionary? A tree or dictionary of … and so on?
Brute force
Generate all 2^n possible subsequences, and check each one against the dictionary for a match. A slight optimization is to at least ensure the dictionary is represented by a hash table or prefix tree so that lookups are efficient.
Check each dictionary word using a greedy algorithm
You can prove that a greedy algorithm works for checking if a word
w is a subsequence of S. Scan S from the beginning for w[0]. After you find it, continue scanning from that point for w[1], and so on, until either you run out of characters in S (w is not a subsequence), or you find all the characters in w (w is a subsequence).
You could sort the dictionary words in order of descending length, run the above decision procedure for each word, and take the first word that is a subsequence of
S. The running time is O(N*W) where W is the number of words in D and N is the number of characters in S.O(N*W) is asymptotically optimal if most dictionary words are close to size N (because then the size of the input is O(N*W)). However, it is far from optimal in a worst-case scenario where S may be long and the dictionary strings quite short.
Define
L to be the total number of characters in the dictionary over all words. Then the best possible time complexity (assuming words shorter than S) is O(N + L). However, the existing algorithm is O(N * W), which might be O(N * L) in the case where dictionary words are a small constant in size.Improving the greedy approach
Notice that to check a dictionary word w, you end up needing to know, for each character
c in w, the least index i in S where S[i] == c, such that i is greater than some given index j (the index of the previously-matched letter). Observe that the greedy algorithm is slow precisely because it naively scans for this index i.
You can preprocess
S to find such indices much faster. Build a map of letter -> sorted list of indices where letter occurs. For example, if S == "abppplee":a -> [0]b -> [1]p -> [2, 3, 4]l -> [5]e -> [6, 7]
When you need to know "Given my last matched character was at index X and my next character to match is Y, where does this match occur?", you would look up
Y in the map, and then binary search the occurrence list to find the smallest number > X in that list, or report that none exists (the word is not a subsequence then).
This approach requires one binary search per dictionary letter. Since it takes only
O(N) time to preprocess S in this way, the total complexity is O(N + L * log N), which is quite close to the best possible complexity.
Advanced approach: You might note that since this is a classic "successor-value" problem, specialized data structures exist that can run the search even faster. A vEB tree, for example, improves the runtime to
O(N + L * log log N).An optimal O(N + L) approach for small alphabets
If the size of the alphabet is a-z or a small constant, we can give a solution based off the previous idea that runs in
O(N + L).
The real complexity is
O(N*A + L), where A is the size of the alphabet. Instead of making the representation sparse, you could make it dense. Instead of p -> [2, 3, 4] you could use p-> [2, 2, 3, 4, -1, -1, -1, -1] where the i-th index directly yields the answer to the query. This requires O(N) space per alphabet letter (O(NA) total) and also that much time during preprocessing. It is therefore not suitable for large alphabets.An optimal O(N + L) approach for any alphabet
Instead of processing the words one at a time, we will process all words simultaneously.
First, for each word
w in D, create a 2-tuple containing w and the number 0 (i.e. (w, 0)). The number refers to the number of characters in w that have already been found in S; initially, no characters have been found. For a tuple t, we'll refer to the word as t.w, and to the number as t.i (since it is an index).
Group the words by
t.w[t.i] (initially t.i is 0, so initially it is by first letter). For our example dictionary D = {"able", "ale", "apple", "bale", "kangaroo"}, we’ll have:a -> [("able", 0), ("ale", 0), ("apple", 0)]b -> [("bale", 0)]k -> [("kangaroo", 0)]
What this is doing is telling you what words you will make progress on finding for each possible letter that you might see next in
S.
Scan
S one character at a time. If the character you just scanned is c, for each tuple t in map[c], increment t.i by 1 and transfer t to map[t.w[t.i]]. The case where t.i ==t.w.length is special - transfer these words to a "found" list. In the end, the output is the longest word in the found listdef find_longest_word_in_string(letters, words):letter_positions = collections.defaultdict(list)# For each letter in 'letters', collect all the indices at which it appears.# O(#letters) space and speed.for index, letter in enumerate(letters):letter_positions[letter].append(index)# For words, in descending order by length...# Bails out early on first matched word, and within word on# impossible letter/position combinations, but worst case is# O(#words # avg-len) * O(#letters / 26) time; constant space.# With some work, could be O(#W * avg-len) * log2(#letters/26)# But since binary search has more overhead# than simple iteration, log2(#letters) is about as# expensive as simple iterations as long as# the length of the arrays for each letter is# “small”. If letters are randomly present in the# search string, the log2 is about equal in speed to simple traversal# up to lengths of a few hundred characters.for word in sorted(words, key=lambda w: len(w), reverse=True):pos = 0for letter in word:if letter not in letter_positions:break# Find any remaining valid positions in search string where this# letter appears. It would be better to do this with binary search,# but this is very Python-ic.possible_positions = [p for p in letter_positions[letter] if p >= pos]if not possible_positions:breakpos = possible_positions[0] + 1else:# We didn't break out of the loop, so all letters have valid positionsreturn word
public String findLongestWordInString(String str, List<String> words) {
Collections.sort(words, new Comp());
char[] chArr = str.toCharArray();
HashMap<Character, List<Integer>> charToIndexeMap = new HashMap();
for (int i = 0; i < chArr.length; i++) {
char c = chArr[i];
if (charToIndexeMap.containsKey(c)) {
charToIndexeMap.get(c).add(i);
} else {
ArrayList<Integer> indexes = new ArrayList<>();
indexes.add(i);
charToIndexeMap.put(c, indexes);
}
}
for (String word : words) {
int pos = 0;
for (Character c : word.toCharArray()) {
List<Integer> possiblePosition = new ArrayList<>();
if (!charToIndexeMap.containsKey(c))
break;
for (Integer p : charToIndexeMap.get(c)) {
if (p >= pos) // use binary search here
possiblePosition = charToIndexeMap.get(c);
}
if (possiblePosition.size() == 0)
break;
pos = possiblePosition.get(0) + 1;
return word;
}
}
return null;
}X.
http://www.cnblogs.com/grandyang/p/6523344.html
上面的方法中用到了sort排序，对于数组中单词的数量不是很多，但是长度特别长的情况很适用，但是如果对于单词数量特别多，但是每个都不长的话，排序的O(nlgn)时间复杂度可能就不是最好的方法了，也可以不用排序来做。我们遍历字典中的单词，然后还是跟上面的方法一样来验证当前单词是否能由字符串s通过删除字符来得到，如果能得到，而且单词长度大于等于结果res的长度，我们再看是否需要更新结果res，有两种情况是必须要更新结果res的，一个是当前单词长度大于结果res的长度，另一种是当前单词长度和res相同，但是字母顺序小于结果res，这两种情况下更新结果res即可
https://discuss.leetcode.com/topic/81474/fast-java-solution-19ms-beats-97-using-indexof/3public String findLongestWord(String s, List<String> d) {
String longest = "";
for (String word : d)
if (isBetter(word, longest) && isSubsequence(word, s))
longest = word;
return longest;
}
private boolean isBetter(String a, String b) {
return a.length() > b.length() ||
a.length() == b.length() && a.compareTo(b) < 0;
}
private boolean isSubsequence(String a, String b) {
int start = -1;
for (int i = 0; i < a.length(); i++){
start = b.indexOf(a.charAt(i), start + 1);
if (start < 0)
return false;
}
return true;
}https://discuss.leetcode.com/topic/80799/short-java-solutions-sorting-dictionary-and-without-sorting
We sort the input dictionary by longest length and lexicography. Then, we iterate through the dictionary exactly once. In the process, the first dictionary word in the sorted dictionary which appears as a subsequence in the input string s must be the desired solution.
public String findLongestWord(String s, List<String> d) {
Collections.sort(d, (a,b) -> a.length() != b.length() ? -Integer.compare(a.length(), b.length()) : a.compareTo(b));
for (String dictWord : d) {
int i = 0;
for (char c : s.toCharArray())
if (i < dictWord.length() && c == dictWord.charAt(i)) i++;
if (i == dictWord.length()) return dictWord;
}
return "";
}
An alternate, more efficient solution which avoids sorting the dictionary:
public String findLongestWord(String s, List<String> d) {
String longest = "";
for (String dictWord : d) {
int i = 0;
for (char c : s.toCharArray())
if (i < dictWord.length() && c == dictWord.charAt(i)) i++;
if (i == dictWord.length() && dictWord.length() >= longest.length())
if (dictWord.length() > longest.length() || dictWord.compareTo(longest) < 0)
longest = dictWord;
}
return longest;
}
Time Complexity: O(nk), where n is the length of string s and k is the number of words in the dictionary.
https://leetcode.com/articles/longest-word-in-dictionary-through-deletion/
- Time complexity : . strings are generated.
- Space complexity : . List contains strings.
public String findLongestWord(String s, List<String> d) {
HashSet<String> set = new HashSet<>(d);
List<String> l = new ArrayList<>();
generate(s, "", 0, l);
String max_str = "";
for (String str : l) {
if (set.contains(str))
if (str.length() > max_str.length() || (str.length() == max_str.length() && str.compareTo(max_str) < 0))
max_str = str;
}
return max_str;
}
public void generate(String s, String str, int i, List<String> l) {
if (i == s.length())
l.add(str);
else {
generate(s, str + s.charAt(i), i + 1, l);
generate(s, str, i + 1, l);
}
}
public String findLongestWord(String s, List<String> d) {
HashSet<String> set = new HashSet<>(d);
List<String> l = new ArrayList<>();
for (int i = 0; i < (1 << s.length()); i++) {
String t = "";
for (int j = 0; j < s.length(); j++) {
if (((i >> j) & 1) != 0)
t += s.charAt(j);
}
l.add(t);
}
String max_str = "";
for (String str : l) {
if (set.contains(str))
if (str.length() > max_str.length() || (str.length() == max_str.length() && str.compareTo(max_str) < 0))
max_str = str;
}
return max_str;
}
X. DFS
The biggest difference of your code to the topic poster's code is you use the dictionary as the pattern and try to fit the string which can be very long (well, the word in the dictionary can also be very long. If the length of the words in the dictionary have the same length with String s, there should be no difference). But @compton_scatter uses the string as the pattern and try to fit the words in the dictionary. I think the test case may affect the result to some extent. And the sorted solution could be more reliable than the unsorted one.
BTW, I also had the TLE problem here, I used Trie though.
BTW, I also had the TLE problem here, I used Trie though.
String max;
public String findLongestWord(String s, List<String> d) {
max = "";
backtrack(s, d, new StringBuilder(), 0);
return max;
}
void backtrack(String s, List<String> d, StringBuilder sb, int start){
if(d.contains(sb.toString())&&sb.length()>max.length()){
max = sb.toString();
}else if(d.contains(sb.toString())&&sb.length()==max.length()){
max = max.compareTo(sb.toString())>0?(sb.toString()):max;
}
for(int i = start;i<s.length();i++){
sb.append(s.charAt(i));
backtrack(s, d, sb, i+1);
sb = sb.deleteCharAt(sb.length()-1);
}
}private void helper(String s, int i, TrieNode curr){
if(curr.word!=null){
if(curr.word.length()>max.length()){
max = curr.word;
}
else if(curr.word.length()==max.length()){
if(curr.word.compareTo(max)<0){
max = curr.word;
}
}
}
if(i==s.length()||curr.maxlen<max.length()) return;
char c = s.charAt(i);
if(curr.children[c-'a']!=null){
helper(s,i+1,curr.children[c-'a']);
}
helper(s,i+1,curr);
}
private void buildTrie(TrieNode root, List<String> d){
for(String s: d){
TrieNode curr = root;
curr.maxlen = Math.max(curr.maxlen,s.length());
for(int i = 0;i<s.length();i++){
char c = s.charAt(i);
if(curr.children[c-'a']==null){
curr.children[c-'a'] = new TrieNode();
}
curr = curr.children[c-'a'];
curr.maxlen = Math.max(curr.maxlen,s.length());
}
curr.word = s;
}
}
class TrieNode{
String word;
TrieNode[] children;
int maxlen;//even adding this var, trying to make the search end earlier, still TLE.
public TrieNode(){
word = null;
maxlen = 0;
children = new TrieNode[26];
}
}