求字符 ‘a‘ 和 ‘b‘ 组成的，最大长度为n的字符串中字典序第 k 个字符串
求字符 ‘a’ 和 ‘b’ 组成的，最大长度为n的字符串中字典序第 k 个字符串
先来解释一下这个题目，假设最大长度为3，那么由字符a和b组成的字符串有：
a, b, ab, aaa, aba...
把这些字符串按照字典序排序:
- a
- aa
- aaa
- aab
- ab
- aba
- abb
- b
- ba
- baa
- bab
- bb
- bba
- bbb
由于只有两个字符，可以用前缀树来存储所有的字符串，对于n=2时的前缀树：
既然用到了树数据结构，这里可以用回溯法的思想来解决这道问题，先遍历左子节点，即先获取字符a，然后再遍历右子节点，即获取字符b
代码如下:
public class KLenString{
public static boolean found;
public static int k;
public static String result;
public static void backtrace(StringBuilder sb, int depth){
if(found){
return;
}
if(sb.length() > 0){
k--;
if(k == 0){
result = sb.toString();
found = true;
return;
}
}
if(sb.length() == depth){
return;
}
sb.append('a');
backtrace(sb, depth);
sb.deletCharAt(sb.length()-1);
sb.append('b');
backtrace(sb, depth);
sb.deletCharAt(sb.length()-1);
}
}
原文地址：https://blog.csdn.net/qq_43539664/article/details/143780807
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！