java - Compute recursively the largest substring which starts and ends with sub and return its length

Question

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.

Examples:

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



}

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

Answer 1

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

}

Now if I do:

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

I get:

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

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.