java - 使用位旋转实现算法来确定字符串是否具有所有唯一字符

Question

我将如何最好地实现一个接受 String 参数并返回true或false取决于 String 是否由所有不同字符组成的 Java 函数。

这是一道面试题。实现应该使用位掩码来存储字符的出现，而不是其他辅助数据结构。

注意：使用位掩码的要求使这个问题不同于：

• 如何确定字符串中的所有字符是否相等

• 确定一个字符串是否具有所有唯一字符？

根据要求，这是我迄今为止的努力。如果可能，请现在重新打开问题：

public static boolean hasAllUniqueCharactersUsingBitMasking(String string) {
  final int length = string.length();
  final int nBitsToStoreAllUnicodeCharacters =
      (int) Math.ceil(Math.log(Character.MAX_CODE_POINT) / Math.log(2d));
  BitSet bitSet = new BitSet(nBitsToStoreAllUnicodeCharacters);
  for (int i = 0; i < length; i++) {
    char c = string.charAt(i);
    if (bitSet.get(c)) {
      return false;
    }
    bitSet.set(c);
  }
  return true;
}

Answer 1

根据破解编码采访：

public static boolean isUniqueChars(String str) {
  if (str.length() > 256) { 
    return false;
  }
  int checker = 0;
  for (int i = 0; i < str.length(); ++i) {
    int val = str.charAt(i) - ‘a’;
    if ((checker & (1 << val)) > 0) return false;
    checker |= (1 << val);
  }
  return true;
}

Answer 2

这是在 Java 中使用 BitSet 类的另一个解决方案。该程序适用于 ASCII 字符集字符串，并且不限制字符串必须为小写或大写。还使用 BitSet 类使其易于使用和理解按位操作。

public static boolean isUniqueStringUsingBitVectorClass(String s) {

        final int ASCII_CHARACTER_SET_SIZE = 256;

        final BitSet tracker = new BitSet(ASCII_CHARACTER_SET_SIZE);

        // if more than  256 ASCII characters then there can't be unique characters
        if(s.length() > 256) {
            return false;
        }

        //this will be used to keep the location of each character in String
        final BitSet charBitLocation = new BitSet(ASCII_CHARACTER_SET_SIZE);

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

            int charVal = s.charAt(i);
            charBitLocation.set(charVal);

            if(tracker.intersects(charBitLocation)) {
                return false;
            }

            tracker.or(charBitLocation);

            charBitLocation.clear(); //clear the individual character tracker for next iteration in the loop

        }

        return true;

    }

Answer 3

public static boolean isUniqueCharsBitSet(String str) {

if (str.length() > 256) {
        return false;
    }

    BitSet set = new BitSet();
    for (int i = 0; i < str.length(); ++i) {
        int val = str.charAt(i) - 'a';
        if (!(set.get(val))) {
            set.set(val);
        } else {
            return false;
        }

    }
    return true;

}