Created
January 28, 2019 22:30
-
-
Save yammik/11faa262514104ae0dbd2c8b19e45074 to your computer and use it in GitHub Desktop.
How to find permutations of substr in a string (problem from CtCI)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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