TopCoder SRM 702 Div1 Medium: RepeatedStrings

問題

• "()" は良い文字列です。
• S を良い文字列としたとき、"(SSS...S)" は良い文字列です。

文字列 S が与えられるので、文字列 S の部分列、かつ、良い文字列のうち、辞書順で k 番目の文字列を返してください。

解法

括弧列に対する様々な先入観から良い文字列の候補が多く感じますが、例えば "(()(()))" は良い文字列ではありません。S が良い文字列であったとき、あくまで S のコピーをいくつか並べたものを括弧で囲ったもののみが良い文字列です。

長さが 150 以下の良い文字列がそもそも 15 万個くらいしかないので、全列挙で間に合います。

コード

import java.util.TreeSet;

public class RepeatedStrings {
  TreeSet<String> G = new TreeSet<>();
  char[] S;

  private boolean isSubSequence(String t) {
    int pos = 0;
    for (char c : S) {
      if (c == t.charAt(pos)) {
        pos++;
        if (pos == t.length()) break;
      }
    }
    return pos == t.length();
  }

  private boolean dfs(String t) {
    if (!isSubSequence(t)) return false;

    G.add(t);
    String good = t;
    while (true) {
      if (dfs("(" + good + ")")) {
        good += t;
      } else
        break;
    }
    return true;
  }

  public String findKth(String s, int k) {
    this.S = s.toCharArray();
    dfs("()");
    for (String t : G) {
      k--;
      if (k == 0) return t;
    }
    return "";
  }
}