Hatena::Grouptopcoder

TopCoder戦記

研究開発者・ellerのTopCoder挑戦記録。言語は主にJavaを使用しています。ドキュメンテーションコメントはSubmit完了後、ブログ掲載前に補完したものです。

2009-09-26SRM428 DIV2

SRM428 DIV2 Level Two(500pt.)

| 00:03

http://www.topcoder.com/stat?c=problem_statement&pm=10180&rd=13519

与えられた文字を並び替え、同じ文字が連続しない文字列をいくつ生成できるか数える。

文字の連続を許さない=計算結果が次回の計算に影響を与える=メモ化が難しく計算量が増えがちですが、地道に総当たりで考えてもTLEにはならずに解くことができます。計算自体は再帰と配列を利用した非常に単純なものです。

public class TheLuckyString {
	public int count(String s) {
		int[] chars = new int[26];
		for (char c : s.toCharArray()) {
			++chars[c - 'a'];
		}
		int count = 0;
		for (int i = 0; i < 26; ++i) {
			if (chars[i] > 0) {
				count += count(chars, i, s.length());
			}
		}
		return count;
	}

	private int count(int[] chars, int last, int length) {
		int count = 0;
		length--;
		chars[last]--;
		if (length == 0) {
			count = 1;
		} else {
			for (int i = 0; i < 26; ++i) {
				if (i == last || chars[i] == 0) {
					continue;
				}
				count += count(chars, i, length);
			}
		}
		chars[last]++;
		return count;
	}
}