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 が「abczzzzxx」または「abczzzz」の場合は true を返しません。誰か提案やアイデアはありますか？

4

4 に答える 4

7

はい - 基本的に、再帰メソッドは常に最後の文字を削除してから、空の文字列を取得するか、値が最初の文字列と等しくなるまで再帰します。

つまり、最初の文字列を見つけることができる唯一の場所は、ターゲット文字列の先頭であり、これは実際にはstartsWithメソッドであることを意味します。

恐ろしく非効率的ですが、うまくいくはずだと私が信じている1つのオプションは、キャラクターを前面から外し、最後からキャラクターを外そうとすることです(独立して):

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 に答える