-
Notifications
You must be signed in to change notification settings - Fork 0
/
substring-concat-words.js
106 lines (91 loc) · 2.74 KB
/
substring-concat-words.js
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
var con = console;
var log = con.log;
/**
* @description https://leetcode.com/problems/substring-with-concatenation-of-all-words/
* @param {string} s
* @param {string[]} words
* @return {number[]}
*/
var findSubstring = function(s, words) {
var sLen = s.length;
var wordsLen = words.length;
var table = {};
var ans = [];
var begin = 0;
var end = 0;
var currwindow = "";
var lastWord = "";
var firstWord = "";
var counter = 0;
var windowLen = words.join("").length;
if (wordsLen == 0 || sLen < windowLen) return ans;
var wordSize = words[0].length;
for (var i = 0; i < wordsLen; i++) {
if (table[words[i]] === undefined) {
table[words[i]] = 1;
counter++;
} else {
table[words[i]]++;
}
}
var tableRef = Object.assign({}, table);
var counterRef = counter;
// log("windowLen:", windowLen);
// log("wordsLen:", wordsLen);
// log("counter:", counter);
// log(JSON.stringify(table));
for (var j = 0; j < wordSize; j++) {
begin = j;
end = j;
table = Object.assign({}, tableRef);
counter = counterRef;
// log("\n");
// log("begin:", begin, "end:", end);
while (end+wordSize-1 < sLen) {
lastWord = s.substr(end, wordSize);
// log("lastWord:", lastWord);
if (table[lastWord] !== undefined) {
table[lastWord]--;
if (table[lastWord] === 0) counter--;
}
// log("table:", table);
// log("currWindowSize:", end+wordSize-begin)
// log("counter:", counter);
if (end+wordSize-begin === windowLen) {
if (counter === 0) {
if (ans.indexOf(begin) < 0) ans.push(begin);
// log("solution = ", "begin:", begin, "substr:", s.substr(begin, end+wordSize-begin));
}
firstWord = s.substr(begin, wordSize);
if (table[firstWord] !== undefined) {
table[firstWord]++;
if (table[firstWord] > 0) counter++;
}
begin += wordSize;
}
end += wordSize;
}
}
return ans;
};
con.clear();
var args = [
// {
// s: "barfoothefoobarman",
// words: ["foo", "bar"]
// },
// {
// s: "wordgoodgoodgoodbestword",
// words: ["word","good","best","word"]
// },
{
s: "mississippi",
words: ["is"]
},
];
// I should cache args.length but also :P
for (var k = 0; k < args.length; k++) {
log("s:", args[k].s, "words:", args[k].words);
log("returns:", findSubstring(args[k].s, args[k].words));
log("\n");
}