TopCoder SRM 405 Level 2 1000
一个理想的字符串，其中每个字母第一次出现的位置N，与这个字母在字符串中出现的次数M是相等的，求给定长度的字符串中最小的一个理想字符串
字符串长度小于100
相当于去搜索1～100中的一组不同的数
加起来等于长度L
同时每个数字都要小于等于比自己小的所有数的和加一
因为L比较小
所以用深搜就可以了
在这个过程中要注意深搜时候需要从大往小搜
这样才能满足“最小的”结果
搜索完之后的字符串构建的步骤因为StringBuffer用的不熟练
反而调试了很久
1 import java.util.*;
2 import java.util.regex.*;
3 import java.text.*;
4 import java.math.*;
5 import java.awt.geom.*;
6
7 public class IdealString
8 {
9 int[] table = new int[26];
10 int finalindex = 0;
11 int L;
12
13 public String construct(int length)
14 {
15 Arrays.fill(table, 0);
16 L = length;
17 if(dfs(1, 0, 0)){
18 StringBuffer sb = new StringBuffer();
19 char c = 'A';
20 int i , j = 0;
21 for(i = 0 ; i < L; ++ i)
22 sb.append(' ');
23 for(i = 0 ; i < finalindex; ++i){
24 sb.setCharAt(table[i] - 1, c ++);
25 table[i]--;
26 }
27 for(i = 0 ; i < L; ++ i){
28 if(sb.charAt(i) != ' ')
29 continue;
30 while(table[j] == 0) j++;
31 sb.setCharAt(i, (char)('A' + j));
32 table[j]--;
33 }
34 return sb.toString();
35 }
36 return new String();
37 }
38
39 boolean dfs(int num, int index, int sum){
40 table[index] = num;
41 int base = num + sum;
42 if(base == L){
43 table[index] = num;
44 finalindex = index + 1;
45 return true;
46 }
47 if(base > L)
48 return false;
49 int total = 0;
50 for(int i = 0 ; i <= index ; ++ i)
51 total += table[i];
52 for(int i = total + 1; i >= num + 1; -- i){
53 if(base + i <= L && dfs(i, index +1, base))
54 return true;
55 }
56 return false;
57 }
58 }