Find Whether Two Strings are Permutation of each other
Objective: Given Two Strings, check whether one string is permutation of other
Input: Two Strings
Output: True or false based on whether strings are permutation of other or not.
"sumit" and "tiums" are permutations of each other. "abcd" and bdea" are not permutations of each other.
Method 1: Time Complexity – O(nlgn)
Sort both the strings and compare it.
Method 2 : Using Hash Map- Time Complexity – O(n)
- Check if both Strings are having the same length, if not , return false.
- Create a Hash Map, make character as key and its count as value
- Navigate the string one taking each character at a time
- check if that character already existing in hash map, if yes then increase its count by 1 and if it doesn’t exist insert into hash map with the count as 1.
- Now navigate the second string taking each character at a time
- check if that character existing in hash map, if yes then decrease its count by 1 and if it doesn’t exist then return false.
- At the end navigate through hash map and check if all the keys has 0 count against it if yes then return true else return false.
Complete Code for Both Methods:
sumit and mtisu are permutation of each other? true xyzab and bayzxx are permutation of each other? false
Top Companies Interview Questions..-
If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.