Checking if two strings are permutations of each other

Question

How to determine if two strings are permutations of each other

Answer 1

• Sort the two strings's characters.
• Compare the results to see if they're identical.

Edit:

The above method is reasonably efficient - O(n*log(n)) and, as others have shown, very easy to implement using the standard Java API. Even more efficient (but also more work) would be counting and comparing the occurrence of each character, using the char value as index into an array of counts.

I do not thing there is an efficient way to do it recursively. An inefficient way (O(n^2), worse if implemented straightforwardly) is this:

• If both strings consist of one identical character, return true
• Otherwise:
  • remove one character from the first string
  • Look through second string for occurrence of this character
  • If not present, return false
  • Otherwise, remove said character and apply algorithm recursively to the remainders of both strings.

Answer 2

To put @Michael Borgwardt's words in to code:

if(str1.length != str2.length)
  return false;

char[] a = Arrays.sort(str1.toCharArray());
char[] b = Arrays.sort(str2.toCharArray());
int len = a.length;

for(i = 0; i < len; ++)
  if(b[i] != a[i])
    return false;

return true;

Answer 3

1. Sort the 2 strings by characters and compare if they're the same (O(n log n) time, O(n) space), or
2. Tally the character frequency of the 2 strings and compare if they're the same (O(n) time, O(n) space).

Answer 4

Create a Hashmap with the characters of the first string as keys and the number of occurances as value; then go through the second string and for each character, look up the hash table and decrement the number if it is greater than zero. If you don't find an entry or if it is already 0, the strings are not a permutation of each other. Obviously, the string must have the same length.

Answer 5

You might take a look at String.toCharArray and Arrays.sort

Answer 6

First you check the lengths (n), if they are not same, they cannot be permutations of each other. Now create two HashMap<Character, Integer>. Iterate over each string and put the number of times each character occur in the string. E.g. if the string is aaaaa, the map will have just one element with key a and value 5. Now check if the two maps are identical. This is an O(n) algorithm.

EDIT with code snippet :

boolean checkPermutation(String str1, String str2) {

char[] chars1 = str1.toCharArray();
char[] chars2 = str2.toCharArray();

Map<Character, Integer> map1 = new HashMap<Character, Integer>();
Map<Character, Integer> map2 = new HashMap<Character, Integer>();

for (char c : chars1) {
   int occ = 1;
   if (map1.containsKey(c) {
       occ = map1.get(c);
       occ++;
   }
   map1.put(c, occ);
}

// now do the same for chars2 and map2

if (map1.size() != map2.size()) {
   return false;
}
for (char c : map1.keySet()) {

    if (!map2.containsKey(c) || map1.get(c) != map2.get(c)) {
        return false;
    }
}

return true;
}

Answer 7

This is the way using sort.but i got to use recursion.

import java.io.*; import java.util.Arrays;

public class perm { public static void main(String[] args) throws IOException {

    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); 

    System.out.print("First string: "); //Input 1st string
    String str1 = reader.readLine(); 
    System.out.print("Second string: "); //Input 2nd string 
    String str2 = reader.readLine(); 

    char[] chars1 = str1.toCharArray(); 
    char[] chars2 = str2.toCharArray(); 

    Arrays.sort(chars1); 
    Arrays.sort(chars2); 
    System.out.println("Second is a permutation of first:" + Arrays.equals(chars1, chars2));//Return true if permutation,return false if not. 
} 

}

Answer 8

I'm working on a Java library that should simplify your task. You can re-implement this algorithm using only two method calls:

boolean arePermutationsOfSameString(String s1, String s2) {
    s1 = $(s1).sort().join(); 
    s2 = $(s2).sort().join();
    return s1.equals(s2);
}

testcase

@Test
public void stringPermutationCheck() {
    // true cases
    assertThat(arePermutationsOfSameString("abc", "acb"), is(true));
    assertThat(arePermutationsOfSameString("bac", "bca"), is(true));
    assertThat(arePermutationsOfSameString("cab", "cba"), is(true));

    // false cases
    assertThat(arePermutationsOfSameString("cab", "acba"), is(false));
    assertThat(arePermutationsOfSameString("cab", "acbb"), is(false));

    // corner cases
    assertThat(arePermutationsOfSameString("", ""), is(true));
    assertThat(arePermutationsOfSameString("", null), is(true));
    assertThat(arePermutationsOfSameString(null, ""), is(true));
    assertThat(arePermutationsOfSameString(null, null), is(true));
}

PS

In the case you can clone the souces at bitbucket.

Answer 9

The obligatory Guava one-liner:

boolean isAnagram(String s1, String s2) {
    return ImmutableMultiset.copyOf(Chars.asList(s1.toCharArray())).equals(ImmutableMultiset.copyOf(Chars.asList(s2.toCharArray())));
}

(Just for fun. I don't recommend submitting this for your assignment.)

Answer 10

import java.io.*;

class Permutation {

public static void main(String args[]) throws IOException {
BufferedReader br = 
new BufferedReader(new InputStreamReader(System.in));
String str,newstr;
System.out.println("enter the string");
str = br.readLine();
System.out.print("The permutations are :");
int len = str.length();
StringBuffer sb = new StringBuffer(str);
    if(len <=1){
System.out.print(str);
    }
else doPerm(sb,len);
    System.out.println("");
    System.out.println("enter the 2nd string");
    newstr = br.readLine();
    if(newstr.equalsIgnoreCase(str)){
        System.out.print("Permutation");
    }
}   

private static void doPerm(StringBuffer str,int index){

    if(index > 2){
doPerm(str,index-1);
}
else{
swap(str);
return; 
}
int len1 =  str.length(); 
StringBuffer s1=new StringBuffer(str);
for(int j = 0;j < index-1; j++){
char t1 = s1.charAt(len1-1-j);
char t2 = s1.charAt(len1-index);
s1.setCharAt(len1-1-j,t2);
s1.setCharAt(len1-index,t1);
doPerm(s1,index-1);
    }
    }

//Swap the last two chars
private static void swap(StringBuffer d){
//Print given String first  
System.out.print(d);
System.out.print("  ");
int length=d.length();
char t1,t2;
t1=d.charAt(length-1);
t2=d.charAt(length-2);
d.setCharAt(length-1,t2);
d.setCharAt(length-2,t1);
System.out.print(d);
System.out.print("  ");
d.setCharAt(length-1,t1);
d.setCharAt(length-2,t2);
}

}

I am doing it this way.now how can i get the strings to be compared to each other?can anyone help me with that?

Answer 11

As you requested, here's a complete solution using recursion. Now all you have to do is:

1. Figure out what language this is
2. Translate it to Java.

Good luck :-)

proc isAnagram(s1, s2);
  return {s1, s2} = {''} or
         (s2 /= '' and
          (exists c = s1(i) |
                  s2(1) = c and
                  isAnagram(s1(1..i-1) + s1(i+1..), s2(2..))));
end isAnagram;

Answer 12

import java.io.*; public class permuterecur {

 public static void main(String[] args) throws IOException {         

String a,b; 

    BufferedReader br = 
        new BufferedReader(new InputStreamReader(System.in));
   System.out.println("enter the 1st string");
a = br.readLine();
System.out.println("enter the 2nd string");
b = br.readLine();
    if (a.length() != b.length()) { 
    System.out.println("Not permutation"); 
} 

int[] charCount = new int[256]; 
for (int i = 0; i < a.length(); ++i) { 
    ++charCount[a.charAt(i)]; 
} 

for (int i = 0; i < b.length(); ++i) { 
    if (--charCount[b.charAt(i)] < 0) { 
        System.out.println("Not permutation"); 
    } 
} 
 System.out.println("permutation"); 

} } I am using this code.But there seems to be a problem with it.it prints"permutation"even when the two strings are not.Any comments?

Answer 13

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;

public class permutcheck {

 public static void main(String[] args) throws IOException {         

String a,b; 

    BufferedReader br = 
        new BufferedReader(new InputStreamReader(System.in));
   System.out.println("enter the 1st string");
a = br.readLine();
System.out.println("enter the 2nd string");
b = br.readLine();
    if (a.length() != b.length()) { 
    System.out.println("Not permutation"); 
} 
int[] charCount = new int[256]; 
for (int i = 0; i < a.length(); ++i) { 
    ++charCount[a.charAt(i)]; 
} 

for (int i = 0; i < b.length(); ++i) { 
    if (--charCount[b.charAt(i)] < 0) { 
        System.out.println("Not permutation"); 
    } 
} 

System.out.println("permutation"); 

}
}

i used this code--but it is case-sensitive.how can i make it case-insensitive