追加のデータ構造を使用したり、小文字の仮定を使用したりせずに、文字列にすべて一意の文字が含まれているかどうかを判断します。

Question

これは質問の 1 つです コーディング面接を突破する 本 ゲイル・ラークマン・マクダウェル著:

文字列にすべての一意の文字が含まれているかどうかを判断するアルゴリズムを実装します。追加のデータ構造を使用できない場合はどうすればよいでしょうか?

著者は次のように書いています。

ビット ベクトルを使用すると、スペースの使用量を少し削減できます。以下のコードでは、文字列は小文字のみであると仮定します。 'a' を通して 'z'. 。これにより、int を 1 つだけ使用できるようになります。

著者は次のような実装を行っています。

public static boolean isUniqueChars(String str) {
    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;
}

「文字列は小文字のみである」という仮定を取り除いたとしましょう。 'a' を通して 'z'」。代わりに、文字列には ASCII 文字や Unicode 文字など、あらゆる種類の文字を含めることができます。

著者と同じくらい効率的な解決策 (または著者と同じくらい効率的な解決策) はありますか?

関連する質問:

• 文字列に一意の文字が含まれているかどうかを検出します。私のソリューションを「コーディング面接を突破する」と比較してみてはいかがでしょうか?
• すべての文字が一意であるかどうかを判断するためのビット ベクトルの使用について説明する
• 文字列の一意の文字
• 文字列にすべての一意の文字が含まれているかどうかを判断するアルゴリズムの実装
• 文字列にすべての一意の文字が含まれているかどうかを判断しますか?

Answer 1

asccii 文字セットの場合、256 ビットを 4 つの long で表すことができます。基本的に配列は手作業でコーディングします。

public static boolean isUniqueChars(String str) {
    long checker1 = 0;
    long checker2 = 0;
    long checker3 = 0;
    long checker4 = 0;
    for (int i = 0; i < str.length(); ++i) {
        int val = str.charAt(i);
        int toCheck = val / 64;
        val %= 64;
        switch (toCheck) {
            case 0:
                if ((checker1 & (1L << val)) > 0) {
                    return false;
                }
                checker1 |= (1L << val);
                break;
            case 1:
                if ((checker2 & (1L << val)) > 0) {
                    return false;
                }
                checker2 |= (1L << val);
                break;
            case 2:
                if ((checker3 & (1L << val)) > 0) {
                    return false;
                }
                checker3 |= (1L << val);
                break;
            case 3:
                if ((checker4 & (1L << val)) > 0) {
                    return false;
                }
                checker4 |= (1L << val);
                break;
        }            
    }
    return true;
}

次のコードを使用して、Unicode 文字の同様のメソッドの本体を生成できます。

static void generate() {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < 1024; i++) {
        sb.append(String.format("long checker%d = 0;%n", i));
    }
    sb.append("for (int i = 0; i < str.length(); ++i) {\n"
            + "int val = str.charAt(i);\n"
            + "int toCheck = val / 64;\n"
            + "val %= 64;\n"
            + "switch (toCheck) {\n");
    for (int i = 0; i < 1024; i++) {
        sb.append(String.format("case %d:\n"
                + "if ((checker%d & (1L << val)) > 0) {\n"
                + "return false;\n"
                + "}\n"
                + "checker%d |= (1L << val);\n"
                + "break;\n", i, i, i));
    }
    sb.append("}\n"
            + "}\n"
            + "return true;");
    System.out.println(sb);
}

Answer 2

必要なのは 1 行だけです...実際には 1 行未満です。

if (str.matches("((.)(?!.*\\1))*"))

これは、否定的な先読みを使用して、各文字が文字列の後半で繰り返されないことを保証します。

これは、入力内のすべての n 文字について、後続のすべての文字 (n 個あります) が等しいかどうか比較されるため、O(n^2) の時間計算量に近づきます。

Answer 3

「追加のデータ構造」の一般的かつ実践的な定義が必要だと思います。直観的には、すべてのスカラー整数やポインターを「データ構造」と呼ぶことは望ましくありません。それは、「追加のデータ構造」の禁止が無意味になるからです。

big-O 表記法から概念を借用することを提案します。「追加のデータ構造」とは、データ セットのサイズに応じて増大する構造です。

この場合、ビット ベクトルがたまたま整数型に収まるため、OP によって引用されたコードには O(1) のスペース要件があるように見えます。しかし、OP が示唆しているように、問題の一般的な形式は実際には O(N) です。

一般的なケースに対する解決策の例は、2 つのポインターとネストされたループを使用して、すべての文字を他の文字と単純に比較することです。スペース要件は O(1) ですが、時間要件は O(N^2) です。

Answer 4

次のようなアルゴリズムはどうでしょうか？

手順:

文字列を小文字に変換します。

文字列内の各文字をループします。

変数データ = 0 を設定します

オフセットを計算 = 文字列の最初の文字の ASCII 値 - 97

マスク = 1 << オフセットを使用してその位置のフラグを設定します

ビット単位の AND が true を返した場合、文字が繰り返されている (マスクとデータ) ため、ここでブレークします。

それ以外の場合は、キャラクターがまだ繰り返されるのを見ていない場合は、ビットワイズまたはデータを実行することで、そのキャラクターのビットを設定します= data |マスク

文字の終わりまで続けます。