Last active
October 10, 2017 02:05
-
-
Save Jwing28/065d8365819146a1dabd2cd2a13c6526 to your computer and use it in GitHub Desktop.
LeetCode: Find the difference
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
/* | |
The first solution I thought of was: | |
turn both strings into arrays | |
sort both strings (js native sort method) | |
loop through the arrays | |
when the letters aren't equal return the letter in the t array | |
or if they're all equal return the letter at the end | |
But using the sort method means the time complexity at worst > O(n). | |
How can I make it O(n)? lets find a solution that doesn't involve sorting. | |
current solution is O(n) time complexity and (I think) O(n) space complexity. | |
*/ | |
var findTheDifference = function(s, t) { | |
var sFreq = {}; | |
var tFreq = {}; | |
s = s.split(""); | |
t = t.split(""); | |
s.forEach(function(letter){ | |
sFreq[letter] = sFreq[letter] + 1 || 1; | |
}); | |
t.forEach(function(letter){ | |
tFreq[letter] = tFreq[letter] + 1 || 1; | |
}); | |
for (var key in tFreq) { | |
if (!(key in sFreq)) { | |
return key; | |
}else { //match | |
if(tFreq[key] !== sFreq[key]) { | |
return key; | |
} | |
} | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Assumed arguments provided to function were not equal and both would be supplied.