14
\$\begingroup\$

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");
    }
}
\$\endgroup\$
  • \$\begingroup\$ Just a quick hint: Whenever you got lines of code that are repeated all over with minor variations such as variable names in your case, use an (additional) array and loop other that instead \$\endgroup\$ – Tobias Kienzler Nov 21 '14 at 14:43
27
\$\begingroup\$

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;
|improve this answer|||||
\$\endgroup\$
  • 4
    \$\begingroup\$ Great answer. Small suggestion: An edge case where one or both parameters are null isn't covered. If both are null I'd return true and if only one is null, false. \$\endgroup\$ – Andrej Nov 20 '14 at 1:54
  • 3
    \$\begingroup\$ Only works for simple characters. Doesn't handle UTF-16 surrogate pairs, combining marks are other kinds of unicode equivalences. \$\endgroup\$ – CodesInChaos Nov 20 '14 at 11:15
  • 2
    \$\begingroup\$ @CodesInChaos Agreed. I assumed this not to be an issue since the code under review only covered lowercase ASCII. \$\endgroup\$ – Robby Cornelissen Nov 20 '14 at 11:17
  • 1
    \$\begingroup\$ You could optimize by taking string length into consideration. \$\endgroup\$ – Matthew Nov 20 '14 at 18:06
  • 2
    \$\begingroup\$ Fair enough :) it's in my answer \$\endgroup\$ – Rune FS Nov 25 '14 at 11:43
7
\$\begingroup\$

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"));
}
|improve this answer|||||
\$\endgroup\$
  • 2
    \$\begingroup\$ That doesn't look right. assertTrue(HelloWorld.same("abd", "bcb")); will succeed while it should not. \$\endgroup\$ – Robby Cornelissen Nov 20 '14 at 2:19
  • \$\begingroup\$ Correct. The check sum approach fails in this case. \$\endgroup\$ – Andrej Nov 20 '14 at 2:23
  • 1
    \$\begingroup\$ Also you can use foreach instead of setting up your own iterator if you like. \$\endgroup\$ – Luke Nov 20 '14 at 17:27
  • 1
    \$\begingroup\$ @LukeWillis this is due to using the Map. Originally it was a for loop only with O(N). \$\endgroup\$ – Andrej Nov 21 '14 at 6:36
  • 1
    \$\begingroup\$ @Andrej HashMaps are constant-time (amortized) for puts and gets. It looks to me like this is still O(N) even in the worst case where the two strings are large, and only differ by one character. This is because the first loop would run in O(N) time, and the second loop would run in up to O(N) time, which is simply O(N) total. \$\endgroup\$ – skeggse Nov 21 '14 at 15:38
4
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ The first 256 primes \$\endgroup\$ – Rune FS Nov 25 '14 at 12:22
4
\$\begingroup\$

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");
}
|improve this answer|||||
\$\endgroup\$
3
\$\begingroup\$

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;
    }
}
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Your final implementation is O(N^2), and thus isn't optimized given that your so-called naive approach is also O(N^2). This might actually be O(N^3) because removing an element from the middle of an array list is O(N), because it has to copy every element in front of the removed element back one. \$\endgroup\$ – skeggse Nov 21 '14 at 15:43
2
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ YOu could just do return counts.sum()==0 which might be a little more effiecent \$\endgroup\$ – Gilsham Nov 20 '14 at 19:22
  • \$\begingroup\$ It wouldn't work to check the sum. string1 could have an 'a' and not an 'm' and string2 could have an 'm' and not an 'a' and the sum would still be zero. \$\endgroup\$ – PatrickSharbaugh Nov 20 '14 at 19:23
  • \$\begingroup\$ I see now, sorry, you could instead sum the absolute value of the array \$\endgroup\$ – Gilsham Nov 20 '14 at 19:26
  • \$\begingroup\$ It wouldn't work since one value in the count could be 1 and the another would be -1. The sum would be zero, but there would be non-zero values in the counts array. \$\endgroup\$ – PatrickSharbaugh Nov 20 '14 at 19:27
  • 1
    \$\begingroup\$ instead of negating the result of any you could simply do return counts.All(x => x == 0) which I personally think expresses the intention better. \$\endgroup\$ – Rune FS Nov 25 '14 at 12:43
2
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.