山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[yukicoder] No.52 よくある文字列の問題

問題

No.52 よくある文字列の問題 - yukicoder

問題の意味が良く分からなかったので解説みて理解しました。

mmxsrup.hatenablog.com

考え方

操作で文字列を作るときは、先頭か末尾の文字を選びその文字を消去します。その文字を繋げて作られる文字列の組み合わせを解答するという問題です。

文字の選び方は 2 通りなので、全体で 2^{|S|} 通りあります。これはビット列に対応させることができます。ビット列はよくでてきますね。

コード

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Exec0052a {
    static int[] bit;
    static String[] a;
    static Set<String> set;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String S = scan.next();
        scan.close();
        a = S.split("");
        bit = new int[a.length];
        set = new HashSet<String>();
        rec(0);
        System.out.println(set.size());

    }
    static void solve() {
        int l = 0;
        int r = a.length - 1;
        String []t = new String[bit.length];
        for(int i = 0; i < bit.length; i++) {
            if(bit[i] == 0) {
                t[i] = a[l];
                l ++;
            }else {
                t[i] = a[r];
                r --;
            }

        }
        set.add(con(t));
    }
    public static void rec(int k) {
        if(k == bit.length) {
            solve();
            return;
        }
        rec(k + 1);
        bit[k] = 1;
        rec(k + 1);
        bit[k] = 0;
    }
    static String con(String[] s) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < s.length; i++) {
            sb.append(s[i]);
        }
        return sb.toString();
    }
}