Check Permutation of string in Java

userNlg41 0
Viewed 37

The Question I have is : For a given two strings, 'str1' and 'str2', check whether they are a permutation of each other or not. Permutations of each other Two strings are said to be a permutation of each other when either of the string's characters can be rearranged so that it becomes identical to the other one.

Example: str1= "sinrtg" str2 = "string"

The character of the first string(str1) can be rearranged to form str2 and hence we can say that the given strings are a permutation of each other. Input Format: The first line of input contains a string without any leading and trailing spaces, representing the first string 'str1'.

The second line of input contains a string without any leading and trailing spaces, representing the second string 'str2'. Note: All the characters in the input strings would be in lower case. Output Format: The only line of output prints either 'true' or 'false', denoting whether the two strings are a permutation of each other or not.

You are not required to print anything. It has already been taken care of. Just implement the function.

My code for this:

public static boolean isPermutation(String str1, String str2) {
    //Your code goes here
    boolean ans=false;
    
    if (str1.length()==str2.length()){
        for (int i=0;i<str1.length();i++){
               ans=false;
            for (int j=0;j<str2.length();j++){
                if (str1.charAt(i)==str2.charAt(j)){
                    ans=true;}
            }
            if (ans == false){
            break;}
    }   
}else{
        return false;
    }
  return ans;
}

One test case is giving me a wrong answer . Cany anybody help which test case will this code not work for ?

java arrays algorithm
1 Answers

Your code checks two things:

  • That str1 and str2 have the same length.
  • For each character in str1, that this character exists in str2.

This does not work, as you found out.

A trivial example is:

  • str1 = "hello"
  • str2 = "ehhlo"

Note how these are not permutations: str2 has 2 h characters and only one l. However, they have the same length, and str2 contains every character in str1.

One convoluted solution is to not just scan for the target letter, but also remove it (use it up). This would be easier if you pile all characters in a list first.

However, there is a vastly simpler way to do all this, and to make the algorithm considerably faster to boot. As this is clearly homework, and not the direct question you asked, I'll simply give you a hint: Is there a thing you can do to both str1 and str2 such that, once that's been done, the question can be answered simply by checking if str1 and str2 are equal?

rzwitserloot0
Related