How to determine if two strings are permutable in java?

Question

I am trying to determine if two strings are a permutation of each other. When I enter the following strings (see code below), the program should print that the two string are permutable. However, this is not the statement that I can see on my screen. Can anyone help me? Here is my code:

public static void main(String[] args) {
    String str1 = "abcrdt";
    String str2 = "barcdt";
    char[] arr1 = str1.toCharArray();
    Arrays.sort(arr1);
    char[] arr2 = str2.toCharArray();
    Arrays.sort(arr2);
    if (isPermutation(arr1, arr2)) {
        System.out.print("The strings are permutable.");
    } else {
        System.out.print("The strings are not permutable.");
    }
}

static boolean isPermutation(char[] arr1, char[] arr2) {
    if (arr1.length != arr2.length) {
        return false;
    }
    for (int i = 0; i <= arr1.length; i++) {
        for (int j = 0; j <= arr2.length; j++) {
            if (arr1[i] != arr2[j]) {
                return false;
            }
        }
    }
    return true;
}

score 1 · Answer 1 · edited Jul 27 '21 at 10:04

Your implemented logic inside the for loop originated the bug. You are using a nested loop where you are checking for each index of arr1 if there is any mismatch of the char with any character in arr2, you're returning false.

For example, if the first char from arr1 is a, you're checking whether it is mismatched with any of the chars from arr2. That's why you're getting retuned false.

Also, even if your logic were okay inside the loop, you'd get an ArrayIndexOutOfBoundException anyways, as you're iterating from index 0 to index including arr.length, where the zero indexed arrays have a valid index upto arr.length-1

To solve this, you can simply check whether their constructed string from sorted array are same:

public static void main(final String[] args) {
    final String str1 = "abcrdt";
    final String str2 = "barcdt";
    if (isPermutation(str1.toCharArray(), str2.toCharArray())) {
        System.out.print("The strings are permutable.");
    } else {
        System.out.print("The strings are not permutable.");
    }
}

static boolean isPermutation(final char[] str1, final char[] str2) {
    Arrays.sort(str1);
    Arrays.sort(str2);
    return new String(str1).equals(new String(str2));
}

Again, you can make this code more minimal if you omit the isPermutation and do a direct check in the if condition:

public static void main(final String[] args) {
    final String str1 = "abcrdt";
    final String str2 = "barcdt";
    char[] arr1 = str1.toCharArray();
    Arrays.sort(arr1);
    char[] arr2 = str2.toCharArray();
    Arrays.sort(arr2);
    if (new String(arr1).equals(new String(arr2))) {
        System.out.print("The strings are permutable.");
    } else {
        System.out.print("The strings are not permutable.");
    }
}

JayC667 · Answer 2 · 2021-07-21T23:01:49.177

As @chrylis-cautiouslyoptimistic- has already hinted at the problem, but this was not solved, here the solution:

You were thinking too deep into the problem, leading to an overly complex solution.

Check this out, this works just fine and is a lot easier:

import java.util.Arrays;

public class Permutat0r {

    public static void main(final String[] args) {
        final String str1 = "abcrdt";
        final String str2 = "barcdt";
        final char[] arr1 = str1.toCharArray();
        Arrays.sort(arr1);
        final char[] arr2 = str2.toCharArray();
        Arrays.sort(arr2);
        if (isPermutation(arr1, arr2)) {
            System.out.print("The strings are permutable.");
        } else {
            System.out.print("The strings are not permutable.");
        }
    }

    static boolean isPermutation(final char[] arr1, final char[] arr2) {
        System.out.println("CA1");
        for (final char c : arr1) {
            System.out.println("\t" + c);
        }
        System.out.println("CA2");
        for (final char c : arr2) {
            System.out.println("\t" + c);
        }

        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

}

score 0 · Answer 3 · 2021-08-03T03:15:39.123

To check if two strings are permutable, i.e. an anagram, you have to compare two sorted arrays of characters of these strings. To do this, since Java 9, you can use the String#codePoints method. This code works with both regular characters and surrogate pairs.

public static void main(String[] args) {
    // regular characters & surrogate pairs
    System.out.println(checkIfAnagram("twowords", "dortwswo")); // true
    System.out.println(checkIfAnagram("", "")); // true
}

/**
 * @param str1 the first string
 * @param str2 the second string
 * @return whether two strings are an anagram
 */
public static boolean checkIfAnagram(String str1, String str2) {
    // check if the input strings are not null
    if (str1 == null || str2 == null) return false;
    // sorted arrays of code points of input strings
    int[] arr1 = str1.codePoints().sorted().toArray();
    int[] arr2 = str2.codePoints().sorted().toArray();
    // check if two sorted arrays are equal
    return Arrays.equals(arr1, arr2);
}

Without using streams you can call the String#toCharArray() and Arrays.sort() methods separately. The result is the same, but there is a bit more code. This is enough for checking the equality of two arrays, but in this case the surrogate pairs will be separated after sorting, and such an array cannot be restored back to a string.

public static boolean checkIfAnagram(String str1, String str2) {
    // check if the input strings are not null
    if (str1 == null || str2 == null) return false;
    // arrays of characters of input strings
    char[] arr1 = str1.toCharArray();
    char[] arr2 = str2.toCharArray();
    // sorting arrays, surrogate pairs will be separated
    Arrays.sort(arr1);
    Arrays.sort(arr2);
    // check if two sorted arrays are equal
    return Arrays.equals(arr1, arr2);
}

^{See also: How can I check if two strings are anagrams?}

How to determine if two strings are permutable in java?

3 Answers3