Skip to content

Commit 267a3fe

Browse files
fishercoder1534fishercoder1534
committed
add 648
1 parent 33a6807 commit 267a3fe

File tree

3 files changed

+157
-0
lines changed

3 files changed

+157
-0
lines changed

‎README.md

+1
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@ Your ideas/fixes/algorithms are more than welcome!
2020

2121
| # | Title | Solutions | Time | Space | Difficulty | Tag | Notes
2222
|-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
23+
|648|[Replace Words](https://leetcode.com/problems/replace-words/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_648.java) | O(n) |O(n) | Medium | Trie
2324
|646|[Maximum Length of Pair Chain](https://leetcode.com/problems/maximum-length-of-pair-chain/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_646.java) | O(nlogn) |O(1) | Medium | DP
2425
|645|[Set Mismatch](https://leetcode.com/problems/set-mismatch/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_645.java) | O(nlogn) |O(1) | Easy |
2526
|644|[Maximum Average Subarray II](https://leetcode.com/problems/maximum-average-subarray-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_644.java) | |O(1) | Hard | Binary Search

‎src/main/java/com/fishercoder/solutions/_648.java

+90
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.List;
4+
5+
/**
6+
* 648. Replace Words
7+
8+
* In English, we have a concept called root,
9+
* which can be followed by some other words to form another longer word
10+
* - let's call this word successor.
11+
* For example, the root an, followed by other, which can form another word another.
12+
* Now, given a dictionary consisting of many roots and a sentence.
13+
* You need to replace all the successor in the sentence with the root forming it.
14+
* If a successor has many roots can form it, replace it with the root with the shortest length.
15+
16+
You need to output the sentence after the replacement.
17+
18+
Example 1:
19+
Input: dict = ["cat", "bat", "rat"]
20+
sentence = "the cattle was rattled by the battery"
21+
Output: "the cat was rat by the bat"
22+
23+
Note:
24+
The input will only have lower-case letters.
25+
1 <= dict words number <= 1000
26+
1 <= sentence words number <= 1000
27+
1 <= root length <= 100
28+
1 <= sentence words length <= 1000
29+
30+
*/
31+
public class _648 {
32+
public String replaceWords(List<String> dict, String sentence) {
33+
String[] tokens = sentence.split(" ");
34+
TrieNode trie = buildTrie(dict);
35+
return replaceWords(tokens, trie);
36+
}
37+
38+
private String replaceWords(String[] tokens, TrieNode root) {
39+
StringBuilder stringBuilder = new StringBuilder();
40+
for (String token : tokens) {
41+
stringBuilder.append(getShortestReplacement(token, root));
42+
stringBuilder.append(" ");
43+
}
44+
return stringBuilder.substring(0, stringBuilder.length()-1);
45+
}
46+
47+
private String getShortestReplacement(String token, final TrieNode root) {
48+
TrieNode temp = root;
49+
StringBuilder stringBuilder = new StringBuilder();
50+
for (char c : token.toCharArray()) {
51+
stringBuilder.append(c);
52+
if (temp.children[c - 'a'] != null) {
53+
if (temp.children[c - 'a'].isWord) {
54+
return stringBuilder.toString();
55+
}
56+
temp = temp.children[c - 'a'];
57+
} else {
58+
return token;
59+
}
60+
}
61+
return token;
62+
}
63+
64+
private TrieNode buildTrie(List<String> dict) {
65+
TrieNode root = new TrieNode(' ');
66+
for (String word : dict) {
67+
TrieNode temp = root;
68+
for (char c : word.toCharArray()) {
69+
if (temp.children[c - 'a'] == null) {
70+
temp.children[c - 'a'] = new TrieNode(c);
71+
}
72+
temp = temp.children[c - 'a'];
73+
}
74+
temp.isWord = true;
75+
}
76+
return root;
77+
}
78+
79+
public class TrieNode {
80+
char val;
81+
TrieNode[] children;
82+
boolean isWord;
83+
84+
public TrieNode(char val) {
85+
this.val = val;
86+
this.children = new TrieNode[26];
87+
this.isWord = false;
88+
}
89+
}
90+
}

‎src/test/java/com/fishercoder/_648Test.java

+66
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._648;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import java.util.Arrays;
8+
import java.util.List;
9+
10+
import static org.junit.Assert.assertEquals;
11+
12+
/**
13+
* Created by stevesun on 7/24/17.
14+
*/
15+
public class _648Test {
16+
private static _648 test;
17+
private static List<String> dict;
18+
private static String sentence;
19+
20+
@BeforeClass
21+
public static void setup(){
22+
test = new _648();
23+
}
24+
25+
@Test
26+
public void test1(){
27+
dict = Arrays.asList("cat", "bat", "rat");
28+
sentence = "the cattle was rattled by the battery";
29+
assertEquals("the cat was rat by the bat", test.replaceWords(dict, sentence));
30+
}
31+
32+
@Test
33+
public void test2(){
34+
dict = Arrays.asList("e","k","c","harqp","h","gsafc","vn","lqp","soy","mr","x",
35+
"iitgm","sb","oo","spj","gwmly","iu","z","f","ha","vds",
36+
"v","vpx","fir","t","xo","apifm","tlznm","kkv","nxyud","j",
37+
"qp","omn","zoxp","mutu","i","nxth","dwuer","sadl","pv","w",
38+
"mding","mubem","xsmwc","vl","farov","twfmq","ljhmr","q","bbzs",
39+
"kd","kwc","a","buq","sm","yi","nypa","xwz","si","amqx","iy","eb",
40+
"qvgt","twy","rf","dc","utt","mxjfu","hm","trz","lzh","lref","qbx",
41+
"fmemr","gil","go","qggh","uud","trnhf","gels","dfdq","qzkx","qxw");
42+
sentence = "ikkbp miszkays wqjferqoxjwvbieyk gvcfldkiavww vhokchxz dvypwyb " +
43+
"bxahfzcfanteibiltins ueebf lqhflvwxksi dco kddxmckhvqifbuzkhstp wc " +
44+
"ytzzlm gximjuhzfdjuamhsu gdkbmhpnvy ifvifheoxqlbosfww mengfdydekwttkhbzenk wjhmmyltmeufqvcpcxg " +
45+
"hthcuovils ldipovluo aiprogn nusquzpmnogtjkklfhta klxvvlvyh nxzgnrveghc mpppfhzjkbucv cqcft " +
46+
"uwmahhqradjtf iaaasabqqzmbcig zcpvpyypsmodtoiif qjuiqtfhzcpnmtk yzfragcextvx ivnvgkaqs " +
47+
"iplazv jurtsyh gzixfeugj rnukjgtjpim hscyhgoru aledyrmzwhsz xbahcwfwm hzd ygelddphxnbh " +
48+
"rvjxtlqfnlmwdoezh zawfkko iwhkcddxgpqtdrjrcv bbfj mhs nenrqfkbf spfpazr " +
49+
"wrkjiwyf cw dtd cqibzmuuhukwylrnld dtaxhddidfwqs bgnnoxgyynol hg " +
50+
"dijhrrpnwjlju muzzrrsypzgwvblf zbugltrnyzbg hktdviastoireyiqf qvufxgcixvhrjqtna ipfzhuvgo daee " +
51+
"r nlipyfszvxlwqw yoq dewpgtcrzausqwhh qzsaobsghgm ichlpsjlsrwzhbyfhm ksenb " +
52+
"bqprarpgnyemzwifqzz oai pnqottd nygesjtlpala qmxixtooxtbrzyorn gyvukjpc s mxhlkdaycskj uvwmerplaibeknltuvd ocnn " +
53+
"frotscysdyclrc ckcttaceuuxzcghw pxbd oklwhcppuziixpvihihp";
54+
assertEquals("i miszkays w gvcfldkiavww v dvypwyb bxahfzcfanteibiltins ueebf " +
55+
"lqhflvwxksi dc k w ytzzlm gximjuhzfdjuamhsu gdkbmhpnvy i mengfdydekwttkhbzenk w " +
56+
"h ldipovluo a nusquzpmnogtjkklfhta k nxzgnrveghc mpppfhzjkbucv c uwmahhqradjtf i z " +
57+
"q yzfragcextvx i i j gzixfeugj rnukjgtjpim h a x h " +
58+
"ygelddphxnbh rvjxtlqfnlmwdoezh z i bbfj mhs nenrqfkbf " +
59+
"spfpazr w c dtd c dtaxhddidfwqs bgnnoxgyynol h " +
60+
"dijhrrpnwjlju muzzrrsypzgwvblf z h q i daee r nlipyfszvxlwqw " +
61+
"yoq dewpgtcrzausqwhh q i k bqprarpgnyemzwifqzz " +
62+
"oai pnqottd nygesjtlpala q gyvukjpc s mxhlkdaycskj " +
63+
"uvwmerplaibeknltuvd ocnn f c pxbd oklwhcppuziixpvihihp", test.replaceWords(dict, sentence));
64+
}
65+
66+
}

0 commit comments

Comments
 (0)