递归计算以sub开头和结尾的最大子串，并返回其长度

Question

任务是：给定一个字符串和一个非空子字符串sub，递归计算以sub开头和结尾的最大子字符串，并返回其长度。

示例:

strDist("catcowcat", "cat") → 9
strDist("catcowcat", "cow") → 3
strDist("cccatcowcatxx", "cat") → 9

你能看看我的代码，告诉我它有什么问题吗？

public int strDist(String str, String sub)
{

  if(str.length()<sub.length())
  return 0;
  if(str.length()==sub.length()&&str.equals(sub))
  return str.length();

  if(str.length()<2)
  {
    if(str.contains(sub))
    {

      return 1;
    }
    return 0;
  }

  if (str.length()==2)
 {
   if (sub.length()==2 && str.equals(sub))
   return 2;
   if (str.contains(sub))
   return 1;
   return 0;
 }

if(str.length()>2)
{
   if(str.startsWith(sub)&&str.endsWith(sub))
   {
     return str.length();
   }
   if(str.substring(0,sub.length()).equals(sub))
   {
    strDist(str.substring(0,str.length()-2),sub);
   }
   if(str.substring(str.length()-sub.length(),str.length()-1).equals(sub))
   strDist(str.substring(1,str.length()-1),sub);
}
  return strDist(str.substring(1,str.length()-1),sub);



}

它不适用于大小写 strDist（“嗨嗨嗨”、“嗨”）→ 5 并返回零。

Answer 1

您的实现很难理解。描述算法比提供实现更合适。

基于描述，下面是我的实现，我觉得简洁易懂。

class Example {

    private static int indexOf(String str, int idx, String sub, int res) {

        if (str.length() < sub.length()) return res;

        int tmp = str.indexOf(sub, idx);

        if (tmp < 0) return res;

        return Math.max(tmp, indexOf(str, tmp + 1, sub, res));

    }

    public static int strDist(String str, String sub) {

        if (str.length() < sub.length()) return 0;


        int from = str.indexOf(sub);
        int to = indexOf(str, from + 1, sub, from);


        return to - from + sub.length();
    }

    public static void main(String[] args) {

        System.out.println();
        System.out.println(strDist("catcowcat", "cat"));
        System.out.println(strDist("catcowcat", "cow"));
        System.out.println(strDist("cccatcowcatxx", "cat"));
        System.out.println(strDist("hiHellohihihi", "hih"));
    }
}

结果：

9
3
9
5

Answer 2

这是我解决它的方法，有点相似，但我发现它更简单（希望有帮助）：

public int strDist(String str, String sub) { 

  if(str.length() < sub.length())
    return 0;

  if(!str.contains(sub))return 0;

  if(str.startsWith(sub)&& str.endsWith(sub))
    return str.length();

  if(str.startsWith(sub) )
    return  strDist(str.substring(0,str.length()-1),sub);

  if(str.endsWith(sub)) 
    return strDist(str.substring(1,str.length()),sub);

  else return strDist(str.substring(1,str.length()-1),sub);
}

Answer 3

首先，为了回答您的问题，我在您的代码中发现了一些问题。下面是我的更正版本，并对我所做的更改进行了评论。

public int strDist(String str, String sub) {

    if (str.length() < sub.length())
        return 0;
    // simplified condition
    if (str.equals(sub))
        return str.length();

    if (str.length() < 2) {
        if (str.contains(sub)) {
            // corrected (if str and sub are both empty strings, you don’t want to return 1)
            return str.length();
        }
        return 0;
    }

    // deleted str.length() == 2 case that didn’t work correctly

    if (str.startsWith(sub) && str.endsWith(sub)) {
        return str.length();
    }
    if (str.startsWith(sub)) { // simplified
        // subtracting only 1 and added return statement
        return strDist(str.substring(0, str.length() - 1), sub);
    }
    // changed completely -- didn’t understand; added return statement, I believe this solved your test case
    if (str.endsWith(sub))
        return strDist(str.substring(1), sub);
    return strDist(str.substring(1, str.length() - 1), sub);

}

现在如果我这样做：

    System.out.println(strDist("catcowcat", "cat"));
    System.out.println(strDist("catcowcat", "cow"));
    System.out.println(strDist("cccatcowcatxx", "cat"));
    System.out.println(strDist("hiHellohihihi", "hih"));

我得到：

9
3
9
5

第二，正如我在评论中所说的，我看不出在这里使用递归有什么意义(也许除了这个练习)。你的方法的以下版本没有，它简单得多，并且工作原理相同:

public int strDist(String str, String sub) {
    int firstOccurrence = str.indexOf(sub);
    if (firstOccurrence == -1) { // sub not in str
        return 0;
    }
    int lastOccurrence = str.lastIndexOf(sub);
    return lastOccurrence - firstOccurrence + sub.length();
}

最后，这可能有帮助，也可能没有帮助，递归版本不需要像您的版本那样复杂：

public int strDist(String str, String sub) {
    if (sub.isEmpty()) {
        throw new IllegalArgumentException("sub mustn’t be empty");
    }
    if (str.length() <= sub.length()) {
        if (str.equals(sub)) {
            return str.length();
        } else { // sub cannot be in str
            return 0;
        }
    }
    if (str.startsWith(sub)) {
        if (str.endsWith(sub)) {
            return str.length();
        } else {
            return strDist(str.substring(0, str.length() - 1), sub);
        }
    } else {
        return strDist(str.substring(1), sub);
    }
}

如果可以的话，先让一些东西工作也没关系，即使它不是最简单和优雅的解决方案。当它工作或不工作时，是想办法简化的好时机。这将更容易确定错误，也便于以后的维护。特殊情况，如长度1和长度2，通常是简化的好选择：看看通用代码是否已经满足它们的要求，或者是否可以轻松实现。