CODEWITHSUNDEEP
stringalgorithm
user1128891
user1128891

Reputation: 23

Similar String Comparison Algorithm

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?

Upvotes: 1

Views: 480

Answers (2)

user6317321
user6317321

Reputation:

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.

Upvotes: 0

ruakh
ruakh

Reputation: 183270

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.

Upvotes: 4

Related Questions