競プロおぼえがき

おぼえがきのためのブログ

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

  • 問題

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

  • 概要

与えられた文字列の前後のどちらかから文字を取ることを文字列がなくなるまで続ける。
取り出した順につなげた文字列を新しい文字列とするときに、新しい文字列は何通り作ることができるか求める。

  • 考え方

普通に全探索。再帰的に関数を呼び出して前後どちらからも取り出す方法を試す。取り終わったらSetに入れておけば同じ文字列の重複はなくなる。
一通り終わったところでsetのサイズを表示して終わり。

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

public class Main {
    static Scanner in = new Scanner(System.in);
    static Set<String> set = new HashSet<>();

    public static void main(String[] args) {
        String s = in.next();
        f(s, "");
        System.out.println(set.size());
    }

    public static void f(String s1, String s2) {
        if (s1.length() == 1) {
            set.add(s2 + s1);
        } else {
            f(s1.substring(0, s1.length() - 1), s2 + s1.charAt(s1.length() - 1));
            f(s1.substring(1, s1.length()), s2 + s1.charAt(0));
        }
    }
}