Skip to content

Instantly share code, notes, and snippets.

@yammik
Created January 28, 2019 22:30
Show Gist options
  • Save yammik/11faa262514104ae0dbd2c8b19e45074 to your computer and use it in GitHub Desktop.
Save yammik/11faa262514104ae0dbd2c8b19e45074 to your computer and use it in GitHub Desktop.
How to find permutations of substr in a string (problem from CtCI)
function excise(str, index) { // helper function to remove char from substr
return str.slice(0, index) + str.slice(index+1);
}
function compare(template, x) { // compares two str of equal length
if (template.length !== x.length) return false;
if (template === x) {
return true;
} else if (template.length === 1) {
return false;
}
const j = x.indexOf(template[0]);
if (j !== -1) {
return compare(template.slice(1), excise(x, j));
}
}
function findSubStr(s, b) {
let results = [];
for (let i = 0; i < b.length; i++) {
if (s.indexOf(b[i]) !== -1) { // start scan for the next s.length - 1 characters
let currentThread = b.slice(i, i+s.length);
if (compare(currentThread, s)) {
results.push(i);
} else continue;
}
}
return results;
}
let s = 'abbc', b = 'cbabadcbbabbcb';
findSubStr(s, b) // => [0, 6, 9]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment