Skip to content

Instantly share code, notes, and snippets.

@akrolsmir
Last active August 18, 2020 00:31
Show Gist options
  • Save akrolsmir/fde5f10e34488e88193e8372b7a7840d to your computer and use it in GitHub Desktop.
Save akrolsmir/fde5f10e34488e88193e8372b7a7840d to your computer and use it in GitHub Desktop.
// Problem: Given a string "line" and a number "xCount", output all versions of the string
// with exactly xCount locations replaced by "X".
// e.g. "abcd", 2 => ["XXcd", "XbcX", "abXX", etc...]
// For each line in lines, replace the character at index with 'X'
function joinLine(index, lines) {
function blot(line) {
return (
line.substring(0, index - 1) + 'X' + line.substring(index, line.length)
);
}
return lines.map(blot);
}
/* Returns a list of all (length CHOOSE xCount) */
function recurseLine(line, xCount, firstIndex) {
// Base case
if (xCount == 0) {
return [line];
}
// Just look at that DP!!!
let lists = [];
for (let i = firstIndex; i <= line.length; i++) {
lists = lists.concat(joinLine(i, recurseLine(line, xCount - 1, i + 1)));
}
return lists;
}
// Test:
recurseLine('abcd', 2, 1);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment