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 <= 104
  • sConsists of lowercase English letters
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • words[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 code

Idea 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 code

Idea 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 code

The 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 code

The 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