递归计算以 sub 开头和结尾的最大子串并返回其长度 [英] Compute recursively the largest substring which starts and ends with sub and return its length

问题描述

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

The task is: Given a string and a non-empty substring sub, compute recursively the largest substring which starts and ends with sub and return its length.

示例:

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

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

Can you please look at my code and tell me what is the problem with it?

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("hiHellohihihi", "hih") → 5并返回零.

it doesn't work for the case strDist("hiHellohihihi", "hih") → 5 and returns zero.

推荐答案

首先，为了回答您的问题，我在您的代码中发现了许多问题.下面是我更正的版本，并附有对我所做更改的评论.

First, to answer your question, I found a number of issues in your code. My corrected version follows, with comments about the changes I did.

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

第二，正如我在评论中所说，我认为在这里使用递归没有意义(除了练习).您的方法的以下版本没有，它更简单并且工作原理相同:

Second, as I said in a comment, I see no point in using recursion here (except perhaps for the exercise). The following version of your method doesn’t, it’s much simpler and it works the same:

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();
}

最后，这可能有用也可能没用，递归版本不需要像你的那么复杂:

Finally, and this may or may not be helpful, a recursive version needs not be as complicated as yours:

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，通常是简化的一个很好的候选:看看通用代码是否已经满足它们或者可以很容易地实现.

It’s fine to get something to work first if you can, even if it’s not the most simple and elegant solution. When either it works or it doesn’t, is a good time to think of ways to simplify. It will make it easier to nail down the bug(s) and also ease maintenance later. Special cases, like length 1 and length 2, are often a good candidate for simplification: see if the general code already caters for them or can easily be made to.

这篇关于递归计算以 sub 开头和结尾的最大子串并返回其长度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！