java - 如何制作 "isSubstring(str1, str2)"的递归 boolean 方法

Question

if (isSubstring(str1, str2))
System.out.println(str1 + " is a substring of " + str2 + ".")

这是 isSubstring 的方法:

public static boolean isSubstring(String str, String target)
    {   
        if (str == target)
            return true;

        return (isSubstring(str, target.substring(0,5)));            
    }

这就是我现在的代码，我无法理解你将如何解决这个问题。我的老师要求我们使用递归，因此返回必须调用自身。通常这个问题只需一行代码就可以轻松解决:

public static boolean isSubstring(String str, String target)
{
return str.contains(target)
}

但是我必须毫无意义地使用递归来解决这个问题，并且知道这种方法是多么微不足道以及我的老师强制我们这样做是多么过于复杂，这让我非常沮丧。我真的不知道从哪里开始，因为“return str.contains(target)”并没有为我如何尝试解决这个问题提供良好的基础。

Answer 1

有几件事:

首先，您的想法是正确的，但您希望使您搜索的“下一个”字符串比当前字符串小一个大小。因此，如果您要查找字符串“Hamburger”，您会先搜索“amburger”，然后再搜索“mburger”。因此，当您重复时，您可能会尝试类似 return isSubstring(str,target.substring(1)) 现在您似乎正在使用数字 5 作为前 5 个字符。这很奇怪，因为当你第一次这样做时，(从汉堡包到汉堡)你将永远无法再这样做。如果你最初的目标是“火腿”，那么你会立即轰炸!不太好。

其次，仅测试是否相等是不够的。以汉堡包为例，如果您正在寻找“冲动”，您会找到“urger”，然后直接转到“rger”。你永远不会有冲动。因此，不要测试 equals，而是使用 beginsWith() 进行测试。 (如果您从后面缩小它，例如从Hamburger到Hamburge再到Hamburg，那么您可以使用endsWith()。)

最后，如果你没有达到目标，你就没有一个好的方法来做什么。如果您的目标为 xyzzy，并且您正在搜索 bob，则您将找不到它。所以你需要一个“基本情况”，我建议将其用作第一行。意思是“如果 token 不可能位于目标中，那么我们立即返回 false”。

这很难，令人沮丧，而且似乎毫无意义。但请记住，他并不是想教您搜索字符串。太傻了，你知道如何搜索字符串!他试图教你递归，这并不容易“掌握”。