使用 java 进行令人费解的递归

Question

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

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

我的解决方案

public int strDist(String str, String sub) {
    int i = sub.length();
    int j = str.length();
    int count = 0;
    if (str.length() == 1 && str.equals(sub)) {
        return 1;
    } else if (str.length() < sub.length() || str.length() <= 1) {
        return 0;
    }

    if (str.substring(0, i).equals(sub)) {
        if (str.substring(str.length() - i, str.length()).equals(sub)) {
            return str.length();
        } else {
            strDist(str.substring(0, str.length() - i), sub);
        }
    } else {
        strDist(str.substring(1, str.length()), sub);
    }

    return 0;
}

告诉我如何更正代码？

Answer 1

我认为这是更好的递归解决方案：

public int strDist(String str, String sub) {
  if (str.length()==0) return 0;
  if (!str.startsWith(sub))
      return strDist(str.substring(1),sub);
  if (!str.endsWith(sub))
    return strDist(str.substring(0,str.length()-1),sub);
  return str.length();
}

Answer 2

这将“递归计算以sub开头和结尾的最大子串，并返回其长度”，如您所述。

public class PuzzlingRecursion {

    static String substringFound = "";

    public static void main(String[] args) {
        String sentence = "catcowcat";
        String substring = "cat";

        int sizeString = findNumberOfStrings(sentence, substring, 0);
        System.out.println("you are searching for: " + substring);
        System.out.println("in: " + sentence);
        System.out.println("substring which starts and ends with sub and return its length is:"+substringFound + ", " + sizeString);

    }

    private static int findNumberOfStrings(String subStringPassed,
            String setenecePassed, int count) {

        if (subStringPassed.length() == 0) {
            return count + 0;
        }
        if (subStringPassed.length() < setenecePassed.length()) {
            return count + 0;
        }
        count++;
        String lastStringMiddle = subStringPassed.replaceAll("(.*?)" + "("
                + setenecePassed + ")" + "(.*?)" + "(" + setenecePassed + ")"
                + "(.*?.*)", "$3");
        if (subStringPassed.contains(setenecePassed)
                && lastStringMiddle.length() != setenecePassed.length()) {
            if (subStringPassed.contains(setenecePassed)
                    && lastStringMiddle.contains(setenecePassed)) {
                // only found one item no pattern but according to the example
                // you posted it should return the length of one word/substring
                count = setenecePassed.length();
                substringFound = subStringPassed;
                return count;
            }
        }
        // makesure the lastSrtringMiddle has the key we are search
        if (!lastStringMiddle.equals(subStringPassed)) {
            subStringPassed = subStringPassed.replaceFirst(setenecePassed, "");
            String lastString = subStringPassed.substring(0,
                    subStringPassed.lastIndexOf(setenecePassed));
            if (null != lastString && !"".equals(lastString)) {
                count = lastStringMiddle.length() + setenecePassed.length()
                        + setenecePassed.length();
                substringFound = setenecePassed + lastStringMiddle
                        + setenecePassed;
                subStringPassed = "";
            }
            return findNumberOfStrings(subStringPassed, setenecePassed, count);
        }
        return count;
    }
}

Answer 3

为什么这需要通过递归来完成？

编辑：修复了处理sub在str中不存在或只存在一次的情况的代码。

public int strDist(String str, String sub) {
  int last=str.lastIndexOf(sub);
  if (last != -1) {
    int first=str.indexOf(sub);
    if (first != last)
      return last - first + sub.length();
    }
  }
  return 0;
}

如果适合这个问题，递归是很好的。在这种情况下，递归不会增加值，为了递归而使用递归来编写它会使代码效率低下。