Does Java Set<String> contains() check for existence of StringBuilder?

Does Java Set<String> contains() know how to check for the existence of StringBuilder?

I am running this problem in Leetcode. "Find Unique Binary String". Note this Question is not about Solving the Leetcode, but understanding why an issue occurs. https://leetcode.com/problems/find-unique-binary-string/description/

> Given an array of strings nums containing n unique binary strings each
> of length n, return a binary string of length n that does not appear
> in nums. If there are multiple answers, you may return any of them.

nums = ["00","01"]

Code Output
"00"

Expected Answers Choice
"10"

Problem:

This code fails at !currentResults.contains(currentString) where currentString is "00" ,when the number exists in the Set.

Changing it to !currentResults.contains(currentString.toString())) will make it succeed. I am trying to understand reason behind this.

Code:

List<String> results = new ArrayList<>();
Set<String> currentResults = new HashSet<>();
String finalString;
int numsLength;

public String findDifferentBinaryString(String[] nums) {
    
    for (String data: nums) {
        currentResults.add(data);
    }
    if (nums.length == 0) {
        return "";
    }
    numsLength = nums.length;
    getDFS(nums, new StringBuilder(""));
    return finalString;
}

public void getDFS(String[] nums, StringBuilder currentString) {
    if (finalString != null ) {
        return;
    }

    if (currentString.length() == numsLength && !currentResults.contains(currentString)) {
        finalString = currentString.toString();
        return;
    }

    if (currentString.length() == numsLength) return;

    for (int i = 0; i <= 1; i++) {
        currentString.append(String.valueOf(i));
        getDFS(nums,currentString);
        currentString.deleteCharAt(currentString.length() - 1);
    }
}

> Does Java Set Contains() know how to check for existence of Stringbuilder?

No, Set.contains(Object o) checks for the existence of an Object that equals.

Quoting:

> Returns true if this set contains the specified element. More formally, returns true if and only if this set contains an element e such that (o==null ? e==null : o.equals(e)).

This means that a StringBuilder type will not satisfy the .equals() clause because it will call String.equals() and StringBuilder will not satisfy a true condition without explicitly calling .toString() first.

There are other cases in the Java language where .toString() is implicitly called, but the .equals() operator for String is not one of those cases.

> (comment) I was hoping it would match set type and give a warning if String type does not match with StringBuilder

Some code editors -- such as IntelliJ -- will try to warn about this, see attached picture:

>

StringBuilder and StringBuffer are mutable and so the equals and hashcode are not overridden in both. So when someone calls the equals method on these references it would internally use == for comparison, which means only the addresses will be checked and not the content.

StringBuilder sb1 = new StringBuilder("ABC");
StringBuilder sb2 = new StringBuilder("ABC");

System.out.println(sb1.equals(sb2));

Even though both are having the same value, the output will be false because both references are pointing to a different memory location. So the important and primary thing to understand is that the equals method in StringBuilder and StringBuffer will not check for content.

In the case of a Set, the contains() method would be internally using equals and hashcode to check for existence. Now, if the object is of type StringBuilder or StringBuffer the equals would compare the addresses of the contents in the Set and the argument of the contains() method.

So, when we get into your example at this line currentResults.contains(currentString) won't work as you expected, because the Set will be calling equals on the currentString which is a StringBuilder. It will be something like this

currentString.equals(someElementInSet)

And definitely, both currentString and elements in the Set are in different memory locations and would return false.

Now when you call currentResults.contains(currentString.toString())), the value of currentString gets converted to a String type in which equals method checks for content rather than the memory location. So, in this case, if currentString is 00, the contains() will return true.

Areas you can improve

Do the length check of nums at the beginning of the method, you don't have to run a loop if it is empty.

Great question, as this is contrary to some framework methods which utilize the Object parameter.
In these cases, they are extrapolating the StringBuilder through String#valueOf.

The difference is that the Collections Framework is simply disseminating the object type, and not the content.

> "Does Java Set contains() know how to check for the existence of StringBuilder? ...
>
> ... Changing it to !currentResults.contains(currentString.toString())) will make it succeed. I am trying to understand reason behind this. ..."

You're implying that Set#contains should interpret the content of StringBuilder&mdash;i.e., currentString.toString().

This isn't the case.&nbsp; It's just comparing the object type.

Here is the code, ultimately executed by HashSet#contains.
GitHub &ndash; jdk/src/java.base/share/classes/java/util/HashMap.java