Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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...