detect duplicate character in string

Question

I am doing the exercises in the Cracking The Coding Interview book and I am trying to determine if there is a duplicate character in a string. I am using the ArrayList data structure. My method is of return type Boolean, which returns true if there is a duplicate and returns false if there is no duplicate character. I added a third return statement so the program would compile but it always returns false.

import java.util.*;

public class QuestionOneCrackingCode {

    public static void main(String[] args) {
        String s = "abcdefga";
        ArrayList<String> c = new ArrayList<String>();
        c.add(s);

        System.out.print(check(c));
    }

    public static boolean check(ArrayList<String> g) {
        for (int i = 0; i < g.size(); i++) {
            for (int j = i + 1; j < g.size(); j++) {
                if (g.get(i) == g.get(j)) {
                    return true;
                } else {
                    return false;
                }
            }
        }
        return false;
    }
}

Answer 1

您不是将字符串分隔为字符，而是创建一个包含字符串的单元素列表。无需对算法进行重大更改，您可以这样做：

public static void main(String[] args) {
    String s = "abcdefga";

    System.out.print(check(s));
}

public static boolean check(CharSequence g) {
    for (int i = 0; i < g.length(); i++) {
        for (int j = i + 1; j < g.length(); j++) {
            if (g.charAt(i) == g.charAt(j)) {
                return true;
            }
        }
    }
    return false;
}

请注意，第一个return false;也是不正确的，因为它会阻止算法继续进行第一个比较。

顺便说一句，当您比较字符串时，您应该使用.equals()而不是==.

Answer 2

在 Java 8 中，你可以这样做：

public static boolean check(CharSequence checkString)
{
  return checkString.length() != checkString.chars().distinct().count();
}

即，如果字符串中不同字符的数量与字符总数不同，您就知道存在重复项。这不一定是最有效的方法，但它很简洁。

Answer 3

您的解决方案比较列表中的字符串引用。该列表本身仅包含一个字符串。

请尝试以下操作：

// check one string for duplicate chars
public static boolean check(String checkString)
{
    // result flag
    boolean foundDuplicate = false;
    // get string length
    int stringLength = checkString.length();
    // create a set for all found characters (max size is number
    // of characters in the string to check
    Set<Character> characters = new HashSet<>(stringLength);
    // loop all characters in string
    for (int i = 0; i < stringLength; i++)
    {
        // construct a object (may be use internal JDK cache)
        Character c = Character.valueOf(checkString.charAt(i));
        // check if character is already found
        if (characters.contains(c))
        {
            // yes, set result to TRUE
            foundDuplicate = true;
            // break the loop
            break;
        }
        else
        {
            // not found, add char to set
            characters.add(c);
        }
    }
    return foundDuplicate;
}

这受到字符串长度和堆大小的限制。但我假设所有 UTF-8 字符都可以放入堆中。

@Maarten Bodewes 你是对的。检查可以简化为：

        // add character to set and check result
        if (!characters.add(c))
        {
            // returned false: character already exists
            foundDuplicate = true;
            // break the loop
            break;
        }
        // no else necessary