Got this question in a recent interview. Basic String compare with a little twist. I have an input String, STR1 = 'ABC'. I should return "Same/Similar" when the string to compare, STR2 has anyone of these values - 'ACB' 'BAC' 'ABC' 'BCA' 'CAB' 'CBA' (That is same characters, same length and same no of occurrences). The only answer struck at that moment was to proceed with 'Merge sort' or 'Quick Sort' since it's complexity is logarithmic. Is there any other better algorithm to achieve the above result?
-
The worst-case complexity of Quicksort is actually quadratic; it's just that it's a very fast simple and algorithm, so it tends to outperform n log n algorithms for reasonably small values of n.ruakh– ruakh2016-05-10 21:47:44 +00:00Commented May 10, 2016 at 21:47
-
2Use a look-up table. O(N).Karoly Horvath– Karoly Horvath2016-05-10 21:50:59 +00:00Commented May 10, 2016 at 21:50
-
1Also, the best sorting algorithms are average-case nlogn, not logarithmic. Unless we know something about the dataChris– Chris2016-05-10 21:59:54 +00:00Commented May 10, 2016 at 21:59
Add a comment
|
2 Answers
Sorting both, and comparing the results for equality, is not a bad approach for strings of reasonable lengths.
Another approach is to use a map/dictionary/object (depending on language) from character to number-of-occurrences. You then iterate over the first string, incrementing the counts, and iterate over the second string, decrementing them. You can return false as soon as you get a negative number.
And if your set of possible characters is small enough to be considered constant, you can use an array as the "map", resulting in O(n) worst-case complexity.
5 Comments
shole
Sorry if I misunderstood your solution, does it mean that str1 = "ABC", str2 = "AZBZC" will return "Same / Similar"?
ruakh
@shole: No, since the first
Z would instantly result in -1. That said, I just gave a very high-level description, leaving some details to be filled in. In a language/framework like C++/Java/JavaScript/Perl/Python/PHP/Ruby/Standard ML/OCaml/.Net where the length of the string is knowable in O(1), you'd want to pre-compare the lengths for equality; in a language like Haskell or C, you'd want to track the lengths as you iterate, so that you can return false if they turn out not to have matched.shole
I feel like maybe I misunderstood the question, if str1 = "ABC", str2 = "AZBZCZABC", it should return "Similar" right? If yes, I just do not understand how your solution result so...no offense
ruakh
@shole: No, the question specifies that it should only return "Same/Similar" if the two strings have the same lengths (among other criteria).
shole
OK I got it now..I thought it was like searching permutations of str1 as patterns in string2...have to use rabin-karp or aho-corasick, etc...and that'w why I wonder why everyone's solution is simple as O(n), mapping, look-up table....So basically counting sort is the answer..Thanks!!
Supposing you can use any language, I would opt for a python 'dictionary' solution. You could use 2 dictionaries having as keys each string's characters. Then you can compare the dictionaries and return the respective result. This actually works for strings with characters that appear more than once.