Determining whether two scrambled strings are equivalent

Question

I was able to complete the problem doing it in this manner, but I would assume there has to be an easier way.

Sample input:

abc, cba

Output:

Both strings of characters are equivalent.

Or

abc, acc

Output:

Different

---

import java.util.Scanner;

public class StringTest {

    public static void main(String[] args) {
        String str1, str2;
        int aCount = 0, bCount = 0, cCount = 0, dCount = 0, eCount = 0, fCount = 0, gCount = 0, hCount = 0, iCount = 0, jCount = 0, kCount = 0, lCount = 0, mCount = 0, nCount = 0, oCount = 0, pCount = 0, qCount = 0, rCount = 0, sCount = 0, tCount = 0, uCount = 0, vCount = 0, wCount = 0, xCount = 0, yCount = 0, zCount = 0;
        int aCount2 = 0, bCount2 = 0, cCount2 = 0, dCount2 = 0, eCount2 = 0, fCount2 = 0, gCount2 = 0, hCount2 = 0, iCount2 = 0, jCount2 = 0, kCount2 = 0, lCount2 = 0, mCount2 = 0, nCount2 = 0, oCount2 = 0, pCount2 = 0, qCount2 = 0, rCount2 = 0, sCount2 = 0, tCount2 = 0, uCount2 = 0, vCount2 = 0, wCount2 = 0, xCount2 = 0, yCount2 = 0, zCount2 = 0;
        Scanner input = new Scanner(System.in);

        System.out
                .println("Enter your first string that you want compared (lowercase only):");

        str1 = input.next();
        str1 = str1.trim();
        char[] charArr1 = str1.toCharArray();

        System.out
                .println("Enter your second string that you want compared (lowercase only):");

        str2 = input.next();
        str2 = str2.trim();
        char[] charArr2 = str2.toCharArray();

        input.close();

        for (int i = 0; i < charArr1.length; i++) {
            if (charArr1[i] == 'a')
                aCount++;
            if (charArr1[i] == 'b')
                bCount++;
            if (charArr1[i] == 'c')
                cCount++;
            if (charArr1[i] == 'd')
                dCount++;
            if (charArr1[i] == 'e')
                eCount++;
            if (charArr1[i] == 'f')
                fCount++;
            if (charArr1[i] == 'g')
                gCount++;
            if (charArr1[i] == 'h')
                hCount++;
            if (charArr1[i] == 'i')
                iCount++;
            if (charArr1[i] == 'j')
                jCount++;
            if (charArr1[i] == 'k')
                kCount++;
            if (charArr1[i] == 'l')
                lCount++;
            if (charArr1[i] == 'm')
                mCount++;
            if (charArr1[i] == 'n')
                nCount++;
            if (charArr1[i] == 'o')
                oCount++;
            if (charArr1[i] == 'p')
                pCount++;
            if (charArr1[i] == 'q')
                qCount++;
            if (charArr1[i] == 'r')
                rCount++;
            if (charArr1[i] == 's')
                sCount++;
            if (charArr1[i] == 't')
                tCount++;
            if (charArr1[i] == 'u')
                uCount++;
            if (charArr1[i] == 'v')
                vCount++;
            if (charArr1[i] == 'w')
                wCount++;
            if (charArr1[i] == 'x')
                xCount++;
            if (charArr1[i] == 'y')
                yCount++;
            if (charArr1[i] == 'z')
                zCount++;
        }
        for (int i = 0; i < charArr2.length; i++) {
            if (charArr2[i] == 'a')
                aCount2++;
            if (charArr2[i] == 'b')
                bCount2++;
            if (charArr2[i] == 'c')
                cCount2++;
            if (charArr2[i] == 'd')
                dCount2++;
            if (charArr2[i] == 'e')
                eCount2++;
            if (charArr2[i] == 'f')
                fCount2++;
            if (charArr2[i] == 'g')
                gCount2++;
            if (charArr2[i] == 'h')
                hCount2++;
            if (charArr2[i] == 'i')
                iCount2++;
            if (charArr2[i] == 'j')
                jCount2++;
            if (charArr2[i] == 'k')
                kCount2++;
            if (charArr2[i] == 'l')
                lCount2++;
            if (charArr2[i] == 'm')
                mCount2++;
            if (charArr2[i] == 'n')
                nCount2++;
            if (charArr2[i] == 'o')
                oCount2++;
            if (charArr2[i] == 'p')
                pCount2++;
            if (charArr2[i] == 'q')
                qCount2++;
            if (charArr2[i] == 'r')
                rCount2++;
            if (charArr2[i] == 's')
                sCount2++;
            if (charArr2[i] == 't')
                tCount2++;
            if (charArr2[i] == 'u')
                uCount2++;
            if (charArr2[i] == 'v')
                vCount2++;
            if (charArr2[i] == 'w')
                wCount2++;
            if (charArr2[i] == 'x')
                xCount2++;
            if (charArr2[i] == 'y')
                yCount2++;
            if (charArr2[i] == 'z')
                zCount2++;
        }
        if (aCount == aCount2 && bCount == bCount2 && cCount == cCount2
                && dCount == dCount2 && eCount == eCount2 && fCount == fCount2
                && gCount == gCount2 && hCount == hCount2 && iCount == iCount2
                && jCount == jCount2 && kCount == kCount2 && lCount == lCount2
                && mCount == mCount2 && nCount == nCount2 && oCount == oCount2
                && pCount == pCount2 && qCount == qCount2 && rCount == rCount2
                && sCount == sCount2 && tCount == tCount2 && uCount == uCount2
                && vCount == vCount2 && wCount == wCount2 && xCount == xCount2
                && yCount == yCount2 && zCount == zCount2)
            System.out.println("Both strings of characters are equivilent.");
        else
            System.out.println("Different");
    }
}

Answer 1

This is where the Arrays utility class comes in handy. You can use it to sort the character arrays underlying both strings and then compare the sorted character arrays:

public static boolean equivalent(String s1, String s2) {
    char[] chars1 = s1.toCharArray();
    char[] chars2 = s2.toCharArray();

    Arrays.sort(chars1);
    Arrays.sort(chars2);

    return Arrays.equals(chars1, chars2);
}

This method yields the expected results:

assert equivalent("abc", "cba");
assert !equivalent("abc", "acc");

If there's a possibility for one or both of the input strings to be null, you could add the following two checks to the beginning of the method:

if (s1 == null && s2 == null) return true;
if (s1 == null || s2 == null) return false;

If performance is important, you could also add a string length comparison to avoid unnecessary array sorting:

if (s1.length() != s2.length()) return false;

Answer 2

Consider using this approach.

static boolean same(String s1, String s2)
{
    if (s1 == null && s2 == null) return true;
    if (s1 == null || s2 == null) return false;
    if (s1.length() != s2.length()) return false;

    Map<Character, Integer> m = new HashMap<Character, Integer>();
    long diff = 0;
    for (int i=0; i < s1.length(); i++) {
        Character c1 = s1.charAt(i);
        Character c2 = s2.charAt(i);
        diff += c1 - c2;
        if (!m.containsKey(c1)) m.put(c1, 0);
        m.put(c1, m.get(c1) + 1);
        if (!m.containsKey(c2)) m.put(c2, 0);
        m.put(c2, m.get(c2) - 1);
    }
    if (diff != 0) return false;             // string checksum is different

    Iterator<Map.Entry<Character, Integer>> it = m.entrySet().iterator();
    while (it.hasNext())
        if (it.next().getValue() != 0)
            return false;                    // char count is different     
    return true;
}

Tested with

@Test
public void stringCompare()
{
    assertTrue(HelloWorld.same(null, null));
    assertFalse(HelloWorld.same("abc", null));
    assertFalse(HelloWorld.same(null, "cba"));
    assertFalse(HelloWorld.same("ac", "cba"));

    assertTrue(HelloWorld.same("abc", "cba"));
    assertTrue(HelloWorld.same(
            "Hey this is the same thing!", 
            "!this eyHthing is the sa me"));
    assertFalse(HelloWorld.same("abd", "bcb"));
}

Answer 3

You could use a probabilistic algorithm, one that's usually correct but might once in a while fail.

private static boolean eq(String l1, String l2){
    //if the length are different the result must be false
    if(l1.length() != l2.length()) {return false;}

    char[] c1 = l1.toCharArray();
    char[] c2 = l2.toCharArray();
    long sum1 = 1;
    long sum2 = 1;

    //iterate over the arrays of characters
    for(int i = 0; i<c1.length; i++){
        //from an array of primes take the one corresponding to the character
        int f1 = primes[c1[i]];
        int f2 = primes[c2[i]];

        //multiply the intermediate hash with the prime
        sum1 = sum1 * f1;
        sum2 = sum2 * f2;
    }
    //if the sums match the string are (likely) equivalent
    return sum1 == sum2;
}

I test ran this against Robby's implementation as he suggested. I ran 1,000,000 iterations with strings of 160 characters the execution times for the implementation based on Arrays.equals was between 7s and 10s The execution times for the algorithm in this answer was between 0.5s and 0.6s

They would probably also scale differently since one is based on sort and the other is not. With the tests I've run there's however no really clear evidence of that but I did not run with large strings which would typically be required to see any real differences in scaling.

This algorithm can theoretically produce the wrong result. This would happen if one of the sums overflow and resulted in a new value of 0 the likelihood of which should be 1:64^2 for random input. In the case of one of the sums being zero one could fall back on the Arrays.equals implementation. It is possible that there might be other erroneous situations than the one with an overflow to zero, I haven't tried to prove that only tested a few assumptions empirically

Answer 4

Try utilizing dictionaries like so. (This is untested).

Map<Character, Integer> letterMap1 = new HashMap<Character, Integer>();
Map<Character, Integer> letterMap2 = new HashMap<Character, Integer>();

for (int i = 0; i < charArr1.length; i++) {
    if (!letterMap1.containsKey(charArr1[i])) {
        letterMap1.put(charArr1[i], 0);
    }  else {
        letterMap1.put(charArr1[i], letterMap1.get(charArr1[i]) + 1);
    }
}

for (int i = 0; i < charArr2.length; i++) {
    if (!letterMap2.containsKey(charArr2[i])) {
        letterMap2.put(charArr2[i], 0);
    }  else {
        letterMap2.put(charArr2[i], letterMap2.get(charArr2[i]) + 1);
    }
}

boolean equivalent = true;

if (letterMap1.size() == letterMap2.size()) {
    for (Character c : letterMap1.keySet()) {
        if (!letterMap2.containsKey(c)) {
            equivalent = false;
            break;
        } else {
            if (letterMap1.get(c) != letterMap2.get(c)) {
                equivalent = false;
                break;
            }
        }
    }
} else {
    equivalent = false;
}

if (equivalent) {
    System.out.println("Yes");
} else {
    System.out.println("No");
}

Answer 5

Because your code is a bit amateurish, I'm going to use a different approach to showing a solution, basically, how to arrive at it.

We can think of the two strings as sets of characters. How would a human solve this problem? They would pick the first letter of a string, and see if that letter exists in the second string. If so, they would then cross that letter off. Repeat until you have no letters in the first string remaining.

If you never find a letter in that second string, then you know they can't be equivalent. There are also short cuts you can take by checking for string length and null values.

That basic human approach is shown below. You will quickly realize there are ways to optimize this, such as by sorting the strings in alphabetical order. That means that you don't have to check as many letters before hitting a match. With library functions, you can distill all these optimizations into the short example shown by Robby Cornelissen.

There are more esoteric solutions possible involving dictionaries and hashing, or one-liners using streams and integer summing, but I like keeping things easy to follow.

Here is the naive solution that leads to that:

import java.util.*;

public class TestEquivalence {
    public static void main(String[] args) {
        System.out.println(AreStringsEquivalent("a", "b"));
        System.out.println(AreStringsEquivalent("a", "a"));
        System.out.println(AreStringsEquivalent("aaa", "bbb"));
        System.out.println(AreStringsEquivalent("abc", "abc"));
        System.out.println(AreStringsEquivalent("cba", "abc"));
        System.out.println(AreStringsEquivalent("cba", ""));
        System.out.println(AreStringsEquivalent("", ""));
        System.out.println(AreStringsEquivalent(null, "abc"));
        System.out.println(AreStringsEquivalent(null, ""));
    }

    public static boolean AreStringsEquivalent(String a, String b)
    {
        if (a == null && b == null) return true;

        if (a == null || b == null) return false;

        if (a.length() != b.length()) return false;

        char[] aArray = a.toCharArray();

        List<Character> bList = new ArrayList<Character>();
        for(char c : b.toCharArray()){
            bList.add(c);
        }

        for (int i = 0; i < aArray.length; i++)
        {
            for (int j = 0; j < bList.size(); j++)
            {
                if (aArray[i] == bList.get(j))
                {
                    bList.remove(j);
                    break;
                }

                if (j == bList.size() - 1)
                {
                    return false;
                }
            }
        }

        return true;
    }
}

Answer 6

Runs in O(N).

Sorry, this is C#, but the same idea should work in Java.

    public bool SameCharacters(string string1, string string2)
    {
        var encoding = System.Text.ASCIIEncoding.ASCII;

        Byte[] bytes1 = encoding.GetBytes(string1);
        Byte[] bytes2 = encoding.GetBytes(string2);

        if (string1.Length != string2.Length) return false;

        int[] counts = new int[256];
        for (int i = 0; i < string1.Length; i++)
        {
            counts[bytes1[i]]++;
            counts[bytes2[i]]--;
        }

        foreach (var count in counts)
        {
            if (count != 0) return false;
        }

        return true;
    }

This just takes advantage of the fact that each character has a numeric value. If you wanted to consider more than just ascii, you could replace the count array with a map from int -> int and use a different encoding.

Answer 7

One way is to canonicalize both strings by sorting them and checking that the canonical strings are equal. This approach takes O(n lg n) using a comparison-based sort. A linear time algorithm for this problem exists: keep an array of counts of each letter for both strings. If the two array agree output is YES, it's NO elsewise.