如何在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) {

        if(m <= 0 || n <= 0)

            return "";

        if (x.charAt(m-1) == y.charAt(n-1)) 

            return commonSuffixWithRecursion(x, y, m-1, n-1) + x.charAt(m-1);

        else 

         return "";

    }

这里 m=x.length() and n=y.length()

Answer 3

这是使用递增后缀大小的另一个选项：

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

    int i1 = s1.length() - suffixSize;

    int i2 = s2.length() - suffixSize;

    if (i1 > -1 && i2 > -1 && s1.charAt(i1) == s2.charAt(i2)) {

        return commonSuffixWithRecursion(s1, s2, suffixSize + 1);

    }

    return s1.substring(i1 + 1);

}

下面是一些测试用例：

public static void main(String[] args) {

    System.out.println(commonSuffixWithRecursion("dbc", "abc", 1));    // bc

    System.out.println(commonSuffixWithRecursion("a", "a", 1));    // a

    System.out.println(commonSuffixWithRecursion("ab", "b", 1));   // b

    System.out.println(commonSuffixWithRecursion("a", "b", 1));    // empty

    System.out.println(commonSuffixWithRecursion("a", "bc", 1));    // empty

    System.out.println(commonSuffixWithRecursion("ac", "bc", 1));    // c

    System.out.println(commonSuffixWithRecursion("ac", "bcd", 1));    // empty

    System.out.println(commonSuffixWithRecursion("", "bcd", 1));    // empty

    System.out.println(commonSuffixWithRecursion("bcd", "bcd", 1));    // bcd

}