Objective: Given Two Strings, check whether one string is a permutation of other
Input: Two Strings
Output: True or false based on whether strings are permutations of others 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 exists in a hash map, if yes then increase its count by 1, and if it doesn’t exist insert it into a hash map with the count as 1.
- Now navigate the second string taking each character at a time
- check if that character exists in the hash map, if yes then decrease its count by 1 and if it doesn’t exist then return false.
- At the end navigate through the hash map and check if all the keys have 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