Dee*_*pak 4 java string algorithm recursion
以下是问题陈述:
PS:给定一个字符串和一个非空的子字符串子,递归计算最大的子字符串,它以sub开头和结尾并返回其长度.
Examples:
strDist("catcowcat", "cat") ? 9
strDist("catcowcat", "cow") ? 3
strDist("cccatcowcatxx", "cat") ? 9
下面是我的代码:(没有递归)//因为我发现很难用递归实现.
public int strDist(String str, String sub){
int idx = 0;
int max;
if (str.isEmpty()) max = 0;
else max=1;
while ((idx = str.indexOf(sub, idx)) != -1){
int previous=str.indexOf(sub, idx);
max = Math.max(max,previous);
idx++;
}
return max;
}
Run Code Online (Sandbox Code Playgroud)
它的工作量很少,如下所示,但其他人则返回FAIL.
Expected This Run
strDist("catcowcat", "cat") ? 9 6 FAIL
strDist("catcowcat", "cow") ? 3 3 OK
strDist("cccatcowcatxx", "cat") ? 9 8 FAIL
strDist("abccatcowcatcatxyz", "cat") ? 12 12 OK
strDist("xyx", "x") ? 3 2 FAIL
strDist("xyx", "y") ? 1 1 OK
strDist("xyx", "z") ? 0 1 FAIL
strDist("z", "z") ? 1 1 OK
strDist("x", "z") ? 0 1 FAIL
strDist("", "z") ? 0 0 OK
strDist("hiHellohihihi", "hi") ? 13 11 FAIL
strDist("hiHellohihihi", "hih") ? 5 9 FAIL
strDist("hiHellohihihi", "o") ? 1 6 FAIL
strDist("hiHellohihihi", "ll") ? 2 4 FAIL
你能告诉我代码是什么错误,以及如何返回以sub开头和结尾的最大子字符串及其各自的长度.
有一个简单的解决方案,效率更高.找到子字符串的第一个和最后一个出现,你就得到了答案.无需搜索所有事件.
public int strDist(String str, String sub) {
int first = str.indexOf(sub);
if (first == -1)
return 0;
int last = str.lastIndexOf(sub);
return last - first + sub.length();
}
Run Code Online (Sandbox Code Playgroud)
您的代码的问题是您返回最后一次出现的子字符串的索引.您似乎也试图找到最后一次出现,最后一行应该max - previous
至少,但是您还需要添加子串的长度max - previous + sub.length()
.您还需要移动previous
while循环外部的声明.但是你找到了第二次和最后一次出现之间的距离,如果没有恰好出现2次(例如"foocatbar"
或者"catfoocatbarcat"
),则会失败.
递归地解决这个问题有点过分,首先是因为你不能使用内置String.indexOf()
函数.但由于这是家庭作业,这是一个快速尝试:
public static int indexOf(String str, String sub, int start, int direction) {
if (start < 0 || start > str.length() - sub.length())
return -1;
if (str.substring(start, start + sub.length()).equals(sub))
return start;
return indexOf(str, sub, start+direction, direction);
}
public static int strDistRecursive(String str, String sub) {
int first = indexOf(str, sub, 0, 1);
if (first == -1)
return 0;
int last = indexOf(str, sub, str.length() - sub.length(), -1);
return last - first + sub.length();
}
Run Code Online (Sandbox Code Playgroud)