Created
September 4, 2016 18:38
-
-
Save robertberry-zz/9345abccd09162d8d0419959f958b239 to your computer and use it in GitHub Desktop.
O(n) algorithm for counting permutations of a string in another string
This file contains 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 countChars(word) { | |
var counts = {}; | |
for (var i = 0; i < word.length; i++) { | |
var letter = word[i]; | |
if (letter in counts && counts.hasOwnProperty(letter)) { | |
counts[letter]++; | |
} else { | |
counts[letter] = 1; | |
} | |
} | |
return counts; | |
} | |
function countPermutations(needle, haystack) { | |
if (needle.length > haystack.length) { | |
return 0; | |
} | |
var windowSize = needle.length; | |
var charCountState = countChars(needle); | |
var lettersRemaining = needle.length; | |
var permutations = 0; | |
for (var i = 0; i < haystack.length; i++) { | |
var char = haystack[i]; | |
if (char in charCountState) { | |
charCountState[char]--; | |
if (charCountState[char] >= 0) { | |
lettersRemaining--; | |
} | |
} | |
if (i >= windowSize) { | |
var charDropped = haystack[i - windowSize]; | |
if (charDropped in charCountState) { | |
charCountState[charDropped]++; | |
if (charCountState[charDropped] > 0) { | |
lettersRemaining++; | |
} | |
} | |
} | |
if (lettersRemaining === 0) { | |
permutations++; | |
} | |
} | |
return permutations; | |
} | |
var ALPHABET = 'abcdefghijklmnopqrstuvwxyz'; | |
function randomCharacter() { | |
return ALPHABET[Math.floor(Math.random() * 26)]; | |
} | |
function randomWord(length) { | |
var word = ""; | |
for (var i = 0; i < length; i++) { | |
word += randomCharacter(); | |
} | |
return word; | |
} | |
function sortWord(word) { | |
return word.split('').sort().join(''); | |
} | |
function bruteForceCountPermutations(needle, haystack) { | |
var windowSize = needle.length; | |
var sortedNeedle = sortWord(needle); | |
var lastIndex = haystack.length - windowSize + 1; | |
var permutations = 0; | |
for (var i = 0; i < lastIndex; i++) { | |
if (sortWord(haystack.substr(i, windowSize)) === sortedNeedle) { | |
permutations++; | |
} | |
} | |
return permutations; | |
} | |
function runTests(needleSize, haystackSize, numberOfTests) { | |
var correctCount = 0; | |
var failedCount = 0; | |
for (var i = 0; i < numberOfTests; i++) { | |
var needle = randomWord(needleSize); | |
var haystack = randomWord(haystackSize); | |
var quickResult = countPermutations(needle, haystack); | |
var slowResult = bruteForceCountPermutations(needle, haystack); | |
if (quickResult === slowResult) { | |
correctCount++; | |
} else { | |
console.log("countPermutations(" + needle + ", " + haystack +") => " + quickResult + " but expected " + slowResult); | |
failedCount++; | |
} | |
} | |
if (failedCount) { | |
console.log(failedCount + "/" + numberOfTests + " failed."); | |
} else { | |
console.log(numberOfTests + " passed."); | |
} | |
} | |
// e.g. runTests(5, 50, 10000); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment