计算以相同子字符串开头和结尾的最大子字符串的长度

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开头和结尾的最大子字符串及其各自的长度.

mar*_*cog 8

有一个简单的解决方案,效率更高.找到子字符串的第一个和最后一个出现,你就得到了答案.无需搜索所有事件.

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)

http://ideone.com/3mgbK

您的代码的问题是您返回最后一次出现的子字符串的索引.您似乎也试图找到最后一次出现,最后一行应该max - previous至少,但是您还需要添加子串的长度max - previous + sub.length().您还需要移动previouswhile循环外部的声明.但是你找到了第二次和最后一次出现之间的距离,如果没有恰好出现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)

http://ideone.com/f6bok