确定字符串是否具有唯一字符

Question

该问题要求“实现一个算法来确定字符串是否具有所有唯一字符。

我看到了解决方法，但是不是很明白。

public boolean isUniqueChars(String str) {
    if (str.length() > 256) return false;
    boolean[] char_set = new boolean[256];
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i);
        if (char_set[val])
            return false;
        char_set[val] = true;
    }
    return true;
}

难道代码前面不使用parseInt或(int)转换器吗？（str.charAt[i]会自动变成int吗？） boolean[] char set=new boolean[256] 是什么意思？为什么要设置char_set[val]=true?

Answer 1

请参阅我在评论中的解释，因为你只标记了 algorithm 我假设没有语言，只是解决算法本身：

public boolean isUniqueChars(String str){

   //more than 256 chars means at least one is not unique
   //please see first comment by @Domagoj as to why 256 length
    if(str.length()>256) return false;  

        //keeping an array to see which chars have been used
        boolean[] char_set = new boolean[256];

        //iterating over the string
        for(int i=0; i<str,length;i++){

            //not sure what language this is, but let's say it returns an
            //int representation of the char
            int val=str.charAt(i);

            //meaning this has been set to true before, so this char is not unique
            if(char_set[val]) 
                //nope, not unique
                return false;

            //remember this char for next time
            char_set[val]=true;
        } 

    //if we reached here, then string is unique
    return true;
}

Answer 2

想想你会如何用纸和铅笔来做这件事。

写一次字母表。

然后逐个字符地检查你的字符串。

当您遇到一个字符时，将其从字母表中划掉。

如果你去划掉一个字符，发现它已经被划掉了，那么你就知道这个字符之前出现在你的字符串中，你就可以停止了。

这基本上就是您发布的代码所做的，使用数组。该操作在 O(N) 时间内完成，额外的 O(K) space（其中 K 是您拥有的键数）。

如果您的输入有大量元素，或者您无法提前知道它们是什么，您可以使用 hash table 来跟踪哪些元素已经出现。这又需要 O(N) 时间和 O(cK) 额外 space，其中 K 是键的数量，c 是大于 1 的某个值。

但是哈希表可能会占用相当多的 space。还有另一种方法可以做到这一点。对数组进行排序，这将花费 O(N log N) 时间，但需要 no 额外 space。然后遍历数组检查是否有任何两个相邻字符相同。如果是这样，你有一个副本。

Answer 3

我们也可以使用HashSet数据结构来判断string是否包含java.

中的所有唯一字符

Set testSet = new HashSet();

for (int i = 0; i < str.length(); i++) {
    testSet.add(new Character(str.charAt(i)));
}

if (testSet.size() == str.length()) {
    System.out.println("All charcaters are Unique");
} else {
    System.out.println("All charcaters are niot unique");
}

Answer 4

一个简单的解决方案是将String 转换为Set 并比较相应对象的长度。使用 java 8:

private static boolean checkUniqueChars(String copy) {
    if(copy.length() <= 1) return true;
    Set<Character> set = copy.chars()
       .mapToObj(e->(char)e).collect(Collectors.toSet());
    if (set.size() < copy.length()){
        return false;
    }
    return true;
}

Answer 5

你可以在我的博文中看到详细的解释： Check if string has all unique characters

最简单的解决方案是对所有字符进行循环，使用 hashMap 并将每个字符放入 hashmap table，在此之前检查字符是否已经存在。如果字符已经存在，则它不是唯一的。

Answer 6

public class CheckStringUniqueChars {

    public static boolean checkUnique(String str) {
        int i=0,j=str.length()-1;
        while(i<j) {
            if(str.charAt(i) == str.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

Answer 7

一种方法是通过位。

时间复杂度：O(N)（你也可以说时间复杂度是 0(1)，因为 for 循环永远不会迭代超过 128 个字符。)
Space 复杂度：O(1)

将每个字符视为位（无论是否存在）。例如，我们需要检查 "abcada" 中的所有字符是否都是唯一的，所以如果我们要检查一个字符的位是否已经打开，如果是，那么我们 return false 否则设置该位.

现在我们该怎么做？所有的字符都可以表示为数字，然后是位。我们将使用 "set bit" 和 "get bit" 方法。

我们假设，在下面的代码中，字符串只使用小写字母 a 到 z。

public static boolean isUniqueChars(String str) {
    int mask = 0;
    for (int i = 0; i < str.length(); ++i) {
        int val = str.charAt(i) - 'a'; // you will get value as 0, 1, 2.. consider these as the positions inside your mask which you need to check if the bit is set or not
        if ((mask & (1 << val)) > 0) return false; // Check if the bit is already set
        mask |= (1 << val); // Set bit
    }
    return true;
}

想了解位操作，可以参考

https://www.hackerearth.com/practice/notes/bit-manipulation/

https://snook.ca/archives/javascript/creative-use-bitwise-operators

我花了一段时间才理解其中的内容，但一旦我理解了，就大开眼界。你可以用比特解决这么多问题，提供最优解。

Answer 8

public class UniqueString {

public static void main(String[] args) {

    String input = "tes";
    Map<String, Integer> map = new HashMap<String, Integer>();

    for (int i = 0; i < input.length(); i++) {

        if (!map.containsKey(Character.toString(input.charAt(i)))) {
            map.put(Character.toString(input.charAt(i)), 1);
        } else {            
            System.out.println("String has duplicate char");
            break;
        }
    }   
}

}

Answer 9

Java 东南 9

您可以简单地将字符串的长度与不同元素的计数相匹配。为了获得所有字符的IntStream，您可以使用String#chars，您可以在其上应用Stream#distinct来获得唯一元素的Stream。确保将字符串转换为单一大小写 (upper/lower)，否则函数 Stream#distinct 将无法计算不同情况下的相同字符（例如 I 和 i）作为一个。

演示：

import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) {
        // Test
        Stream.of(
                    "Hello", 
                    "Hi", 
                    "Bye", 
                    "India"
                ).forEach(s -> System.out.println(s + " => " + hasUniqueChars(s)));
    }

    static boolean hasUniqueChars(String str) {
        return str.toLowerCase().chars().distinct().count() == str.length();
    }
}

输出：

Hello => false
Hi => true
Bye => true
India => false

Java 东南 8

static boolean hasUniqueChars(String str) {
    return Arrays.stream(str.toLowerCase().split("")).distinct().count() == str.length();
}

Answer 10

为了获得最佳性能，您应该使用 Set, and add the characters of the string to the set. If the set.add(...) 方法 returns false，这意味着给定的字符之前已经出现过，因此您 return false，否则你 return true 添加所有字符后

对于简单的解决方案，使用 Set<Character>:

public static boolean allUniqueCharacters(String input) {
    Set<Character> unique = new HashSet<>();
    for (int i = 0; i < input.length(); i++)
        if (! unique.add(input.charAt(i)))
            return false;
    return true;
}

然而，这将无法处理 BMP 之外的 Unicode 字符，例如 Emojis，因此我们可能希望更改设置以使用 Unicode 代码点：

public static boolean allUniqueCodePoints(String input) {
    Set<Integer> unique = new HashSet<>();
    return input.codePoints().noneMatch(cp -> ! unique.add(cp));
}

然而，即使代码点也不代表我们人类认为的“字符”。为此，我们需要处理字素簇：

public static boolean allUniqueClusters(String input) {
    BreakIterator breakIterator = BreakIterator.getCharacterInstance(Locale.US);
    breakIterator.setText(input);
    Set<String> unique = new HashSet<>();
    for (int start = 0, end; (end = breakIterator.next()) != BreakIterator.DONE; start = end)
        if (! unique.add(input.substring(start, end)))
            return false;
    return true;
}

或 Java 9+:

public static boolean allUniqueClusters(String input) {
    Set<String> unique = new HashSet<>();
    return Pattern.compile("\X").matcher(input).results()
                  .noneMatch(m -> ! unique.add(m.group()));
}

确定字符串是否具有唯一字符

determine if string has unique characters

java

string

algorithm

char

unique

Java 东南 9

Java 东南 8