递归等减法Java

Question

我有以下问题：

编写一个递归静态方法isSubstring，签名如下-

public static boolean isSubstring(String s1,String s2)

获取两个字符串-s1、s2，如果s2是s1的子字符串，则返回true。

该方法应该是递归的，完全不使用迭代。也可以使用您编写的任何其他方法（如果您编写的话）。

正确的答案不会改变方法类型签名/注释（即使通过重载也不会）。

您只能在解决方案中使用以下方法：

公共字符字符（int i）

公共int长度（）

公共字符串子字符串（int i）

这就是我目前所拥有的，我知道它不起作用isSubstring（“hello”，“ho”）将返回true。知道该怎么做吗？

public static boolean isSubstring(String s1, String s2) {
    if (s2.length() == 0)
        return true;
    if ((s1.length() == 0) || (s1.length() < s2.length()))
        return false;
    if (s1.charAt(0) != s2.charAt(0))
        return isSubstring(s1.substring(1), s2);
    else
        return isSubstring(s1.substring(1), s2.substring(1));
}

Answer 1

您的解决方案几乎是好的，但您必须记住您做了一个替代。我提出以下解决方案（使用一个带有不同原型的helper函数，它符合问题的要求）：

public static boolean sub(final String s1, final String s2, final boolean hasReplaced) {
    if (s2.length() == 0) {
        return true;
    }
    if ((s1.length() == 0) || (s1.length() < s2.length())) {
        return false;
    }
    if (s1.charAt(0) != s2.charAt(0)) {
        if (hasReplaced) {
            return false;
        }
        return sub(s1.substring(1), s2, hasReplaced);
    }
    return sub(s1.substring(1), s2.substring(1), true);
}

public static boolean isSubstring(final String s1, final String s2) {
    return sub(s1, s2, false);
}

Answer 2

我想这个应该可以。

它使用了一种辅助方法。当您看到第一个匹配时，它将调用辅助方法并验证子字符串是否从该点匹配。如果不是，它会在下一个匹配中尝试同样的方法。

public static boolean isSubstring(final String s1, final String s2) {
    if (s2.length() == 0) {
        return true;
    }

    if ((s1.length() == 0) || (s1.length() < s2.length())) {
        return false;
    }

    if (s1.charAt(0) != s2.charAt(0)) {
        return isSubstring(s1.substring(1), s2);
    }

    if (!isSubstringAux(s1.substring(1), s2.substring(1))) {
        return isSubstring(s1.substring(1), s2);
    }

    return true;
}

public static boolean isSubstringAux(final String s1, final String s2) {
    if (s2.length() == 0) {
        return true;
    }

    if (s1.charAt(0) == s2.charAt(0)) {
        return isSubstringAux(s1.substring(1), s2.substring(1));
    }

    return false;
}