问题描述
给定一个字符串 F，这个字符串是通过对某个初始字符串 S 执行若干次以下操作得到的：
- 选择一个整数 K（其中 0≤K<∣S∣0≤K<∣S∣，∣S| 表示字符串 S 的长度）
- 将 S 从第 K个位置（从0开始计数）到末尾的子串追加到 S 的末尾，即：S=S+S[K:]
输入格式
- 输入为一个字符串 F，仅包含小写字母，长度不超过 1000。
输出格式
- 输出一个字符串，表示可能的最短初始字符串 S。
- 如果无法通过题目描述的操作得到字符串 F，则输出原字符串 F。
测试样例
样例1：
输入：
str1 = "abbabbbabb"
输出："ab"
解释：初始字符串
"ab"可以通过以下步骤得到最终字符串：
- K=1K=1：
"a[b]"→"a[b][b]"- K=0K=0：
"[abb]"→"[abb][abb]"- K=2K=2：
"ab[babb]"→"ab[babb][babb]"
样例2：
输入：
str1 = "abbbabbbb"
输出："ab"
解释：初始字符串
"ab"可以通过以下步骤得到最终字符串："a[b]"→"a[b][b]""ab[b]"→"ab[b][b]""[abbb]"→"[abbb][abbb]""abbbabb[b]"→"abbbabb[b][b]"
样例3：
输入：
str1 = "jiabanbananananiabanbananananbananananiabanbananananbananananbananananbanananan"
输出：'jiaban'
样例4：
输入：
str1 = "selectecttectelectecttectcttectselectecttectelectecttectcttectectelectecttectcttectectcttectectcttectectcttect"
输出：'select'
样例5：
输入：
str1 = "discussssscussssiscussssscussssdiscussssscussssiscussssscussssiscussssscussss"
输出：'discus'
样例6：
输入：
str1 = "lflsdjlskjflskjfl"
输出：'lflsdjlskjfl'
提示
- 考虑如何判断一个字符串是否可以通过题目描述的操作得到
- 可以尝试从短到长枚举可能的初始字符串
- 时间复杂度应不超过 O(n2)，其中 n 为输入字符串的长度
思路：直接递归搜索每一种可能性，时间复杂度很高，标签是贪心，没有什么思路，只能使用递归解决，个人觉得动态规划也可以做，可以试下。
public class Main {
public static String solution(String str1) {
//直接正向思考测试是否能进行转换
//特殊情况
if(str1.equals("")) return "";
String s = "" + str1.charAt(0);
if(s.repeat(str1.length()).equals(str1)) return s;
//进行遍历判断
for(int i = 2; i <= str1.length();i++){
String str = str1.substring(0,i);
if(get(str,str1)){
return str;
}
}
return "ab";
}
public static boolean get(String str, String target) {
//核心实现
// 进行一个递归出口判断
if (!target.startsWith(str)) {
return false;
} else {
if (str.length() == target.length()) {
return true;
}
}
// 进行一个判断
for (int i = 0; i < str.length(); i++) {
int count = str.length();
if (str.length() < target.length())//防止进入死循环
str = str + str.substring(i);
if (get(str, target)) {
return true;
} else {
// 当前的添加不正确，进行回溯寻找下一个路径
str = str.substring(0,count);
}
}
return false;
}
public static void main(String[] args) {
// Add your test cases here
System.out.println(solution("abbabbbabb").equals("ab"));
System.out.println(solution("abbbabbbb").equals("ab"));
System.out.println(solution("jiabanbananananiabanbananananbananananiabanbananananbananananbananananbanananan").equals("jiaban"));
System.out.println(solution("selectecttectelectecttectcttectselectecttectelectecttectcttectectelectecttectcttectectcttectectcttectectcttect").equals("select"));
System.out.println(solution("discussssscussssiscussssscussssdiscussssscussssiscussssscussssiscussssscussss").equals("discus"));
}
}