Find Whether Two Strings are Permutation of each other

Objec­tive: Given Two Strings, check whether one string is per­mu­ta­tion of other

Input: Two Strings

Out­put: True or false based on whether strings are per­mu­ta­tion of other or not.

Exam­ple:

"sumit" and "tiums" are permutations of each other.

"abcd" and bdea" are not permutations of each other.

Approach:


Method 1: Time Com­plex­ity — O(nlgn)

Sort both the strings and com­pare it.

Method 2 : Using Hash Table — Time Com­plex­ity — O(n)

  • Check if both Strings are hav­ing the same length, if not , return false.
  • Cre­ate a Hash Table, make char­ac­ter as key and its count as value
  • Nav­i­gate the string one tak­ing each char­ac­ter at a time
  • check if that char­ac­ter already exist­ing 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 nav­i­gate the sec­ond string tak­ing each char­ac­ter at a time
  • check if that char­ac­ter exist­ing in hash table, if yes then decrease its count by 1 and if it doesn’t exist then return false.
  • At the end nav­i­gate through hash table and check if all the keys has 0 count against it if yes then return true else return false.

Com­plete Code:


Out­put:

sumit and mtisu are permutation of each other? true
xyzab and bayzxx are permutation of each other? false

You may also like...