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));