This is the 30th day of my participation in the August Text Challenge.More challenges in August
The title
Leetcode-cn.com/problems/su…
Given a string s and some words ** of the same length. ** Find the starting position of the substring in S that happens to be formed by concatenating all the words in words.
Note that the substring must match exactly the words in words, without any other characters in the middle, but you do not need to consider the sequence in which words are concatenated.
Example 1:
Enter: s = “barfoothefoobarman”, words = [“foo”,”bar”]
Output: [0, 9]
Explanation: Substrings starting at index 0 and 9 are “barfoo” and “foobar” respectively. The order of the outputs is not important, [9,0] is also a valid answer.
Example 2:
Enter: s = “wordgoodGoodGoodBestWord “, words = [“word”,”good”,”best”,”word”]
Output: []
Example 3:
Enter: s = “barfoofoobarthefoobarman”, words = [“bar”,”foo”,”the”]
Output:,9,12 [6]
Tip:
1 <= s.length <= 104sConsists of lowercase English letters1 <= words.length <= 50001 <= words[i].length <= 30words[i]Consists of lowercase English letters
Their thinking
Idea 1, sliding Windows
/ * * *@param {string} s
* @param {string[]} words
* @return {number[]}* /
var findSubstring = function(s, words) {
let left = 0,right = 0,wordsLen = words.length;
if(wordsLen == 0) return [];
let res = [];
let gapLen = words[0].length;
let needs = {};
let windows = {};
for(let i = 0; i < wordsLen; i++){ needs[words[i]] ? needs[words[i]]++ : needs[words[i]] =1;
}
let needsLen = Object.keys(needs).length;
let match = 0;
for(let i = 0; i < gapLen; i++){ right = left = i; match =0;
while(right <= s.length - gapLen){
let c1 = s.substring(right,right + gapLen);
right += gapLen;
windows[c1] ? windows[c1]++ : windows[c1] = 1;
if(windows[c1] === needs[c1]){
++match;
}
while(left < right && match == needsLen){
if(Math.floor((right - left) / gapLen) == wordsLen){
res.push(left);
}
let c2 = s.substring(left,left + gapLen);
left += gapLen;
windows[c2]-- ;
if(needs[c2] && windows[c2] < needs[c2]){
match--;
}
}
}
windows = {};
}
return res;
};
Copy the codeIdea 2
Enter: s = “barfoothefoobarman”, words = [“foo”,”bar”]
Step 1: Iterate through each element of words, cut s from word as the starting point, and get the array of cut fragments allValues = [‘foothe’, ‘foobar’, ‘barfoo’, ‘barman’].
Step 2: Iterate through each element of allValues, cut each element (e.g. ‘foobar’ cut to [‘foo’, ‘bar’]), and sort the array of elements (e.g. [‘foo’, ‘bar’] sorts into [‘bar’, ‘foo’]) and then joins to compose the string to get valuesHadSorts = [‘foothe’, ‘barfoo’, ‘barfoo’, ‘barman’].
Step 3: Sort words, and then combine the sorted words into a string W using join method.
Step 4: Walk through each element of valuesHadSorts to determine if it is equal to W and get their index if it is.
var findSubstring = function(s, words) {
const findIndexs = (str, p) = > {
var positions = []
var pos = str.indexOf(p)
while (pos > -1) {
positions.push(pos)
pos = str.indexOf(p, pos + 1)}return positions
}
const getValues = (s, word, sliceLength) = > {
let arr = []
let indexs = findIndexs(s, word)
indexs.forEach((index) = > {
if(index ! = = -1) {
let leftStrEnd = index + word.length
let leftStrStart = leftStrEnd - sliceLength
if (leftStrStart >= 0 && leftStrEnd <= s.length) {
let leftStr = s.substring(leftStrStart, leftStrEnd)
arr.push(leftStr)
}
}
})
return arr
}
const getAllValues = (s, words) = > {
let values = []
let wordSets = [...new Set(words)]
for (let i = 0; i < wordSets.length; i++) {
values = values.concat(getValues(s, wordSets[i], words.length * words[0].length))
}
return [...new Set(values)]
}
const isMatch = (value, words) = > {
let arr = []
let v = value.slice()
let len = words[0].length
while (v) {
arr.push(v.substring(0, len))
v = v.substring(len)
}
return arr.sort().join(' ') === words.sort().join(' ')}if(! s || words.length ===0 || s.length < words.length * words[0].length) return []
let arr = []
const values = getAllValues(s, words)
values.forEach((item) = > {
if (isMatch(item, words)) {
arr = arr.concat(findIndexs(s, item))
}
})
return arr
};
Copy the codeIdea 3
If s=”ababaab”,words=[“ab”,”ba”,”ba”],words=[“ab”,”ba”,”ba”],words=[“ab”,”ba”,”ba”] The string “babaab” is resolved as “B,ab,a,ab”, which involves the problem of words combination sorting. Therefore, in order to simplify the difficulty, the unit length of words is fixed, and “babaab” is resolved as “BA, ba,ab”, from which the basic algorithm can be obtained.
function findSubstring(s,words){
let len=0;
let le=0;
for(let i in list){
len+=list[i].length;
le=list[i].length;
}
let rst=[];
let stMap={};
for(let i in list){
if(! stMap[list[i]]){ stMap[list[i]]=1;
}else {
stMap[list[i]]+=1; }}for(let i=0; i<=str.length-len; i++){let st=str.substr(i,len);
let exist=true;
let smap={};
for(let i=0; i<len; i+=le){let s=st.substr(i,le);
if(! smap[s]){ smap[s]=0;
}
smap[s]+=1;
}
let e=0;
for(let k in smap){
if(stMap[k]&&smap[k]==stMap[k]){
e+=1;
}else {
exist=false;
break; }}if(! exist||e==0) {continue;
}
rst.push(i);
}
return rst;
}
Copy the codeThe above code, due to the creation of a large number of JS objects, results in a large number of data operations, the memory consumption is serious, which can simplify the number of object creation, replaced by the attribute initialization pointer:
var findSubstring = function(s, words) {
let len;
if(words.length>0){
len=words[0].length;
}
return existsStr(s,words,len);
};
function initListMap(list){
let map={};
for(let i of list){
if(! map[i]){ map[i]={start:0};
}
map[i].start+=1;
}
return map;
}
function formateListMap(map){
for(let i in map){
map[i]["exist"]=map[i].start; }}function existsStr(str,list,len){
let rst=[];
if(len){
let long=len*list.length;
let listMap=initListMap(list);
for(let i=0; i+long<=str.length; i++){let st=str.substr(i,long);
formateListMap(listMap);
let exist=true;
for(let k=0; k<long; k+=len){let s=st.substr(k,len);
if(listMap[s]&&listMap[s].exist>0){
listMap[s].exist=listMap[s].exist-1;
}else {
exist=false;
break; }}if(! exist){continue; } rst.push(i); }}return rst;
}
Copy the codeThe change is that map resets the attributes when it is repeatedly called, and does not repeatedly create a large number of similar objects, which greatly reduces the consumption of memory. In fact, the operation can be simplified to recursive algorithm due to its repeatability, but big data may lead to stack overflow, so it is not recommended here
The last
I dreamed of traveling with swords
Look at the prosperity of the world
Young heart always some frivolous
Just a man after all
No regrets I go my way
“Front-end brush” No.30