javascript 寻找易位构词起始索引

[sunhengzhe]

给定一个单词 word 和一个字符串 S，找到 S 中的所有 word 及其易位构词（如 abc 与 bca、cab 等）的起始索引

function findAnswer(word, s) {
	// TODO
}

findAnswer('abc', 'abcxabcbacc'); // [0, 4, 6, 7]

[andysongs]

const check = (str1, str2) => {
  return str1.split('').sort().join('') === str2.split('').sort().join('')
}

const findAnswer = (word, s) => {
  // TODO
  if (word.length > s.length) return;
  let length = word.length;
  let i = 0;
  let res = [];
  while (s[i + length - 1]) {
    let sample = s.slice(i, i + length);
    console.log(sample);
    if (check(word, sample)) res.push(i);
    i++;
  }
  return res;
}

console.log(findAnswer('abc', 'abcxabcbacc')); // [0, 4, 6, 7]

[andysongs]

const eat = (s, ch) => {
  // 从字符串s中吃掉字符ch
  let _s = s.split('');
  let index = _s.indexOf(ch);
  if (index === -1) return 0;
  _s.splice(index, 1)
  return _s.join('')
}

const check = (a, b) => {
  let i = 0;
  while (b[i]) {
    // 从a串中逐个吃掉b串中的字符
    a = eat(a, b[i]);
    if (a === 0) return false;
    i++;
  }
  // 吃完了，说明是易位构词
  return true
}

const findAnswer = (word, s) => {
  // TODO
  if (word.length > s.length) return '子串过长';
  let length = word.length;
  let i = 0;
  let res = [];
  while (s[i + length - 1]) {
    let sample = s.substring(i, i + length);
    console.log(word,sample);
    if (check(word, sample)) res.push(i);
    i++;
  }
  return res;
}

console.log(findAnswer('abc', 'abcxabcbacc')); // [0, 4, 6, 7]

[miSunLaughing]

判断是否为易位构词还可以使用charCode

function findAnswer(word, testStr) {
	var charCodeSum = charCodeOfString(word);
	var len = word.length;
	return String.prototype.split.call(testStr, "")
		.reduce(function(a, b, i, arr){
			if (charCodeSum === charCodeOfString(arr.slice(i, i+len).join(''))) {
				a.push(i);
			}
			return a;
		},[]);
}
function charCodeOfString(str){
	return String.prototype.split.call(str, "")
		.reduce(function(a,b){return a + String.prototype.charCodeAt.call(b, 0)}, 0);
}

findAnswer('abc', 'abcxabcbacc'); // [0, 4, 6, 7]

[andysongs]

@miSunLaughing 这个方法会认为"aadd"和"bbcc"是易位构词

[miSunLaughing]

@andysongs 对哦，和为一个数有很多种拆分法

[iLove-Coding]

       function findAnswer(word, s) {
            let indexArr = [];
            let temp = sortStr(word);
            let arr = [];
            let total = s.length + 1 - word.length;

            for (let i = 0; i < total; i++) {
                arr.push(sortStr(s.substring(i, i + word.length)));
            }
     
            for (let j = 0; j < arr.length; j++) {
                if (arr[j] === temp) {
                    indexArr.push(j);
                }
            }
            return indexArr;
        }

         function sortStr(word) {
            let arr = [...word];
            let temp;
            let state = true;
            for (let i = 0; i < arr.length; i++) {
                state = false;
                for (let j = 0; j < arr.length - i - 1; j++) {
                    if (arr[j] > arr[j + 1]) {
                        temp = arr[j + 1];
                        arr[j + 1] = arr[j];
                        arr[j] = temp;

                        state = true;
                    }
                }
                if(!state) break;
            }
            return arr.join("");
        }

        findAnswer('abc', 'abcxabcbacc'); // [0, 4, 6, 7]

[sunhengzhe]

因为词语组成是相同的，可以考虑建立 word 频率字典，只需要单次遍历 s。窗口沿着 s 移动时，只有头尾字符发生了改变，针对两个单词重新计算频率即可。

class FrequenceMap {
	constructor(word) {
		this.map = new Map();
		for (const char of word) {
			this.increment(char);
		}
	}
	
	increment(char) {
		const { map } = this;
		const count = map.get(char) || 0;
		
		if (count === -1) {
			return map.delete(char);
		}
		
		return map.set(char, count + 1);
	}
	
	decrement(char) {
		const { map } = this;
		const count = map.get(char) || 0;
		
		if (count === 1) {
			return map.delete(char);
		}
		
		return map.set(char, count - 1);
	}
	
	isEmpty() {
		return this.map.size === 0;
	}
	
	clear() {
		this.map.clear();
	}
}

function findAnswer(word, s) {
	const result = [];
	const fm = new FrequenceMap(word);
	const sLen = s.length;
	const wordLen = word.length;
	
	const firstStr = s.slice(0, wordLen);
	
	for (const c of firstStr) {
		fm.decrement(c);
	}
	
	if (fm.isEmpty()) {
		result.push(0);
	}
	
	for (let i = 1; i < sLen - wordLen + 1; i++) {
		const preChar = s[i - 1];
		const nextChar = s[i + wordLen - 1];
		
		fm.increment(preChar);
		fm.decrement(nextChar);
		
		if (fm.isEmpty()) {
			result.push(i);
		}
	}
	
	return result;
}

console.log(findAnswer('abc', 'abcxabcba'))  // [0, 4, 6];