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 Table — Time Complexity — O(n)
- Check if both Strings are having the same length, if not , return false.
- Create a Hash Table, 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 table, if yes then increase its count by 1 and if it doesn’t exist insert into hash table with the count as 1.
- Now navigate the second string taking each character at a time
- check if that character existing in hash table, if yes then decrease its count by 1 and if it doesn’t exist then return false.
- At the end navigate through hash table and check if all the keys has 0 count against it if yes then return true else return false.
sumit and mtisu are permutation of each other? true xyzab and bayzxx are permutation of each other? false