1

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

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。有没有人有任何建议或想法？

4

4 回答 4

7

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

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

一种效率极低但我认为应该有效的选择是尝试将一个角色从前面拿走，然后尝试从最后（独立地）拿走一个角色：

return isSubstring(str, target.substring(0, target.length() - 1))
    || isSubstring(str, target.substring(1));
于 2012-11-08T15:59:29.917 回答
0

尝试

public static boolean isSubstring(String str, String target) {
            System.out.println("target :" + target);
            if (str.equals(target))
                return true;
            else if (str.length() > target.length())
                return false;
            else
                return (isSubstring(str, target.substring(1, target.length())))
                        || (isSubstring(str,
                                target.substring(0, target.length() - 1)));
        }

这应该递归地尝试来自目标的所有子字符串。

于 2012-11-08T16:10:44.043 回答
0

目前，您只能从字符串末尾删除字符。您的函数可以正确调用startsWith(...)

对于子字符串匹配，我会尝试以下算法：

在没有匹配的情况下从主字符串中删除字符。当它们匹配时开始使用两个字符串，直到您匹配子字符串的所有连续字符，或者直到您找到一个不匹配的字符，这将允许您更早停止。

像这样的东西：

boolean isSubString(String s1, String s, boolean match) {
   if (s1 == "") return true; 
   if (s == "") return false;
   if ((s1.charAt(0) != s.charAt(0)) && match) return false; //failfast
   if (s1.charAt(0) == s.charAt(0)) return isSubString(s1.substring(1), s.substring(1), true);
   return isSubString(s1.substring(1), s.substring(1), match);
}

boolean isSubString(String s1, String s) {
    return isSubString(s1, s,false);
}
于 2012-11-08T16:17:41.263 回答
0

我遇到了一个挑战，只能用 charAt()、length() 和 substring() 编写这种函数，这是我写的，我认为它工作正常......

public static void main(String[] args)
{
    System.out.println(isSubstring("pgram", "program")); // Expected: false
    System.out.println(isSubstring("string", "substring")); // Expected: true
    System.out.println(isSubstring("zzz", "zzzabcdef")); // Expected: true
    System.out.println(isSubstring("zzz", "abczzzxx")); // Expected: true
    System.out.println(isSubstring("zzz", "abczzz")); // Expected: true
    System.out.println(isSubstring("hell", "hello")); // Expected: true
    System.out.println(isSubstring("ada", "Madam")); // Expected: true
}

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

    if (target.length() == 0)
        return false;

    if (str.charAt(0) == target.charAt(0)) // "zzz", "zzzabcdef"
    {
        if (str.length() == target.length()) // "zzz", "zzz"
            return isSubstring(str.substring(1), target.substring(1));

        else if (target.length() > str.length()) // "zzz", "zzzabcdef"
        {
            boolean r1 = isSubstring(str, target.substring(0, str.length())); // "zzz", "zzzabcdef"
            boolean r2 = isSubstring(str, target.substring(1)); // Or maybe "string", "substring"

            return r1 || r2;
        }
    }

    return isSubstring(str, target.substring(1));
}
于 2021-04-29T21:19:55.243 回答