-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathConcatenatedWordsV2.js
More file actions
58 lines (50 loc) · 1.88 KB
/
Copy pathConcatenatedWordsV2.js
File metadata and controls
58 lines (50 loc) · 1.88 KB
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
50
51
52
53
54
55
56
57
58
// https://leetcode-cn.com/problems/concatenated-words/
var Test = require('./Common/Test');
var findAllConcatenatedWordsInADict = function (words) {
words.sort((a, b) => a.length - b.length);
const result = [];
for (let i = 0; i < words.length; i++) {
const word = words[i];
if (word.length > 0) {
if (backTracing(word, i)) result.push(word);
}
}
return result;
function backTracing(word, endIndex) {
return doBackTracing(0);
function doBackTracing(start) {
if (start == word.length) {
return true;
}
else {
for (let i = 0; i < endIndex; i++) {
const anotherWord = words[i];
if (anotherWord != "" && anotherWord != word && word.startsWith(anotherWord, start)) {
if (doBackTracing(start + anotherWord.length)) return true;
}
}
return false;
}
}
}
};
function test(words) {
Test.test(findAllConcatenatedWordsInADict, words);
}
function testWithTestcase(id) {
Test.testWithTestcase(findAllConcatenatedWordsInADict, id);
}
// test([""]);
// test(["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"]);
// https://leetcode-cn.com/submissions/detail/88748444/testcase/
// testWithTestcase(88748444);
// https://leetcode-cn.com/submissions/detail/88750509/testcase/
// testWithTestcase(88750509);
// https://leetcode-cn.com/submissions/detail/88752755/testcase/
// testWithTestcase(88752755);
// https://leetcode-cn.com/submissions/detail/88754775/testcase/
// testWithTestcase(88754775);
// https://leetcode-cn.com/submissions/detail/88761915/testcase/
testWithTestcase(88761915);
// ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"]
// ["cat", ""]