java - isSubstring递归方法

Question

下面是调用递归方法的代码:

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

这是我到目前为止完成的方法，它几乎可以工作:

public static boolean isSubstring(String str, String target)
{   
    if (target.length() == 0)
        return false;

    if (str.equals(target))
        return true;

    else     
        return (isSubstring(str, target.substring(0,target.length()-1)));            
}

因此，如果将 str1 作为“zzz”传递，将 str2 作为“zzzabcdef”传递，则它会返回 true。但是，如果 str2 是“abczzzxx”或“abczzz”，它不会返回 true。有没有人有任何建议或想法？

Answer 1

是的 - 基本上你的递归方法总是只是去掉最后一个字符，然后递归，直到它有一个空字符串或者值等于第一个字符串。

这意味着它可以找到第一个字符串的唯一可能位置是目标字符串的开头，这意味着它实际上是一个startsWith 方法。

一个效率极低但我认为应该可行的选项是尝试从前面去掉一个字符并尝试从末尾(独立地)去掉一个字符:

return isSubstring(str, target.substring(0, target.length() - 1))
    || isSubstring(str, target.substring(1));