如何在java中使用递归查找公共后缀

Question

所以我在 Stack Overflow 上看到，可以使用不使用递归的方法派生公共后缀。我很好奇我是否可以通过递归实现同样的效果。尝试使用以下代码但得到 java.lang.StackOverflowError。有人可以帮忙吗？

public static String commonSuffixWithRecursion(String s1, String s2) {

    if(s1.length()==0 || s2.length()==0) {

        return "Strings are empty";

    }

    if(s1.charAt(s1.length()-1)==s2.charAt(s2.length()-1)) {

        return s1.length()-1 + commonSuffixWithRecursion(s1,s2);

    }

    return "No common Suffix";

}

Answer 1

当没有通用后缀时，它应该返回空字符串。您可以subString用来获取下一轮的输入当前字符应附加在下一次运行结果之后示例代码：public static String commonSuffixWithRecursion(String s1, String s2) {    if (s1.length() == 0 || s2.length() == 0) {        return "";    }    if (s1.charAt(s1.length() - 1) == s2.charAt(s2.length() - 1)) {        String nextS1 = s1.substring(0, s1.length() - 1);        String nextS2 = s2.substring(0, s2.length() - 1);        return commonSuffixWithRecursion(nextS1, nextS2 ) + s1.charAt(s1.length() - 1);    }    return "";}测试用例：public static void main(String[] args) {    System.out.println(commonSuffixWithRecursion("dbc", "abc"));    // bc    System.out.println(commonSuffixWithRecursion("a", "a"));    // a    System.out.println(commonSuffixWithRecursion("ab", "b"));   // b    System.out.println(commonSuffixWithRecursion("a", "b"));    // empty}

Answer 2

递归执行的一种简单方法是public static String commonSuffixWithRecursion(String x, String y, int m, int n) {&nbsp; &nbsp; &nbsp; &nbsp; if(m <= 0 || n <= 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return "";&nbsp; &nbsp; &nbsp; &nbsp; if (x.charAt(m-1) == y.charAt(n-1))&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return commonSuffixWithRecursion(x, y, m-1, n-1) + x.charAt(m-1);&nbsp; &nbsp; &nbsp; &nbsp; else&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return "";&nbsp; &nbsp; }这里 m=x.length() and n=y.length()

Answer 3

这是使用递增后缀大小的另一个选项：public static String commonSuffixWithRecursion(String s1, String s2, int suffixSize) {&nbsp; &nbsp; int i1 = s1.length() - suffixSize;&nbsp; &nbsp; int i2 = s2.length() - suffixSize;&nbsp; &nbsp; if (i1 > -1 && i2 > -1 && s1.charAt(i1) == s2.charAt(i2)) {&nbsp; &nbsp; &nbsp; &nbsp; return commonSuffixWithRecursion(s1, s2, suffixSize + 1);&nbsp; &nbsp; }&nbsp; &nbsp; return s1.substring(i1 + 1);}下面是一些测试用例：public static void main(String[] args) {&nbsp; &nbsp; System.out.println(commonSuffixWithRecursion("dbc", "abc", 1));&nbsp; &nbsp; // bc&nbsp; &nbsp; System.out.println(commonSuffixWithRecursion("a", "a", 1));&nbsp; &nbsp; // a&nbsp; &nbsp; System.out.println(commonSuffixWithRecursion("ab", "b", 1));&nbsp; &nbsp;// b&nbsp; &nbsp; System.out.println(commonSuffixWithRecursion("a", "b", 1));&nbsp; &nbsp; // empty&nbsp; &nbsp; System.out.println(commonSuffixWithRecursion("a", "bc", 1));&nbsp; &nbsp; // empty&nbsp; &nbsp; System.out.println(commonSuffixWithRecursion("ac", "bc", 1));&nbsp; &nbsp; // c&nbsp; &nbsp; System.out.println(commonSuffixWithRecursion("ac", "bcd", 1));&nbsp; &nbsp; // empty&nbsp; &nbsp; System.out.println(commonSuffixWithRecursion("", "bcd", 1));&nbsp; &nbsp; // empty&nbsp; &nbsp; System.out.println(commonSuffixWithRecursion("bcd", "bcd", 1));&nbsp; &nbsp; // bcd}