🙄

LeetCoding Challenge Oct. 11: Remove Duplicate Letters

2020/10/12に公開

Java

LeetCode

tech

LeetCode October Challenge の 11 日目。

今日の問題は Remove Duplicate Letters。

問題の概要

与えられた文字列から、その文字列で使われている文字をすべて、かつそれぞれ一文字だけ含むサブシーケンスを考える
このサブシーケンスのうち辞書順的に一番小さい文字列を求めよ

考え方

うーむ、適切なアルゴリズムがすぐには思いつかない…
文字列の末尾から先頭の逆順に文字列を走査して、move-to-front リストでその時点のサブシーケンスを管理してみてはどうか 🤔
- 実際に実装してみて何度か submit してみたが、wrong answer 喰らって直すたびに異なるエラーケースに遭遇してしまう 😭
- このやり方は筋が悪そうなので、別の方法を模索しよう…
では、文字列の長さ * 27 の大きさの二次元配列 table を用意し、 table[文字列上の位置] の配列にてその位置以降に文字 a~z が出現する位置を表してみてはどうか？
- 先と同じく、文字列末尾から先頭に向かって走査して table を完成させる前提だよ
- table[文字列上の位置][26] には、その位置以降に出現する文字をビットで記した値を入れておくよ
  - 下位 1 ビット目が a, 2 ビット目が b, という要領だね
- 空間計算量・時間計算量は文字列長を n、アルファベットサイズを k (k = 26) とすると O(n * k) となり、あまり効率的ではないね 🙈
table が完成したら、辞書順に最小のサブシーケンスから順にそれが存在するか否かを table を頼りに文字列をたどって確認してみよう
- 再帰で書けばよさそう
- 最悪の時間計算量は O(k^k) になるのかな… 😱
ひとまず、この table を利用する方法で実装して submit → accept 🤗
- Runtime は 3ms で、これは Your runtime beats 81.40 % of java submissions. らしい。微妙だなあ… 🙄

コード

class Solution {
    public String removeDuplicateLetters(String s) {
        if (s.isEmpty()) {
            return s;
        }

        int[][] table = new int[s.length()][27];
        int[] current = new int[27];
        for (int i = s.length() - 1; i >= 0; i--) {
            int letter = s.charAt(i) - 'a';
            current[letter] = i;
            current[26] |= 1 << letter;

            System.arraycopy(current, 0, table[i], 0, 27);
        }

        int alphabet = current[26];
        for (int letter = Integer.numberOfTrailingZeros(alphabet);
                letter < 26;
                letter += Integer.numberOfTrailingZeros(alphabet >>> (letter + 1)) + 1) {

            StringBuilder result = recursive(s, alphabet, table, current[letter], 0);
            if (result != null) {
                return result.reverse().toString();
            }
        }

        return "";
    }

    StringBuilder recursive(String s, int alphabet, int[][] table, int index, int usedChars) {
        char ch = s.charAt(index);

        usedChars |= 1 << (ch - 'a');
        if (usedChars == alphabet) {
            return new StringBuilder().append(ch);
        }

        if ((table[index][26] | usedChars) != alphabet) {
            // このルートを探索しても解が求まる望みがない
            return null;
        }

        int b = alphabet ^ usedChars;
        for (int letter = Integer.numberOfTrailingZeros(b);
                letter < 26;
                letter += Integer.numberOfTrailingZeros(b >>> (letter + 1)) + 1) {


            StringBuilder result = recursive(s, alphabet, table, table[index][letter], usedChars);
            if (result != null) {
                return result.append(ch);
            }
        }

        return null;
    }
}

問題の概要

考え方

コード

Discussion