9

だから私は一日中この課題を解決しようとしてきましたが、それを得ることができません.

次の関数は 2 つの文字列を受け入れます。2 番目 (1 番目ではない) には*'s (アスタリスク) が含まれる可能性があります。
An*は文字列 (空、1 文字以上) の置換であり、(s2 でのみ) 1 回、2 回、それ以上、またはまったく出現しない可能性があります。別の*( ab**c) に隣接することはできません。それを確認する必要はありません。

public static boolean samePattern(String s1, String s2)

文字列が同じパターンの場合、true を返します。再帰的
で なければならず、ループ、静的およびグローバル変数を使用しないでください。ローカル変数とメソッドのオーバーロードを使用できます。

次のメソッドのみを使用できます: charAt(i)、substring(i)、substring(i, j)、length()。

例:

1: TheExamIsEasy; 2: The*xamIs*y→ 真
1: TheExamIsEasy; 2: Th*mIsEasy*→ 真
1: TheExamIsEasy; 2: *→ 真
1: TheExamIsEasy; 2: TheExamIsEasy→ 真
1: TheExamIsEasy; 2: The*IsHard→ 偽

アスタリスクが検出されるまで、文字を 1 つずつ比較してみました。次に、連続する char ( ) をat positionの文字とcharAt比較して、アスタリスクが空のものかどうかを確認します。のカウンターとして; false の場合 --両方のカウンタとして再帰を続行します。 別のアスタリスクが見つかるか、文字列の終わりまでこれを続けます。i+1s1ii+1s2is1
i+1

わからない、私の脳は物事を見失い、集中できない、何か指針/ヒントはありますか？私は正しい方向にいますか？

また、これを解決するためにバックトラッキング技術が使用されると言われています。

これまでの私のコード（理論的にも仕事をしていません）：

public static boolean samePattern(String s1, String s2) {
    if (s1.equals(s2) || s2 == "*") {
        return true;
    }
    return samePattern(s1, s2, 1);
}
public static boolean samePattern(String s1, String s2, int i)
{
    if (s1.equals(s2))
        return true;
    if (i == s2.length() - 1) // No *'s found -- not same pattern.
        return false;

    if (s1.substring(0, i).equals(s2.substring(0, i)))
        samePattern(s1, s2, i+1);
    else if (s2.charAt(i-1) == '*')
        samePattern(s1.substring(0, i-1), s2.substring(0, i), 1); // new smaller strings.
    else
        samePattern(s1.substring(1), s2, i);
}
4

5 に答える 5

6

役立つかもしれないPythonの「疑似コード」は次のとおりです

def samePattern(s1,s2):
    if s2 == "*" or s1 == s2: return True
    if s1 == "": return False
    if s1[0] == s2[0]: return samePattern(s1[1:], s2[1:])
    if s2[0] == "*": return samePattern(s1, s2[1:]) or samePattern(s1[1:], s2)
    return False

コード変換の目安はこちら

s[0] = the first character
s[1:] = the string minus the first character
于 2010-06-07T00:07:13.740 に答える
5

現在のアプローチの問題は、 * が一致する可能性のあるすべての部分文字列を考慮していないことです。たとえば、samePattern("ababababab", "a*b") は true を返す必要があります。* は文字列の最初と最後の文字を除くすべてに一致しますが、コードでは、次の文字が b であるため、* は空の文字列に一致すると想定しています。

samePattern は、一致を探すときに 2 つの入力文字列を「消費」するものと考えることをお勧めします。各ステップで、samePattern は各文字列の最初の文字だけを調べて、最初の文字での一致が可能かどうかを判断し、可能であれば再帰呼び出しを行って文字列の残りを確認する必要があります。パターン文字列で * に達したときに何をすべきかを知ることが秘訣です。これは、s1 の最初の文字との一致に使用される場合と使用されない場合があるためです。何をすべきかを決めるために、残りの文字列を見る必要はありません。

これは宿題なので、そこで何が起こっているのかを詳しく説明するのはやめておきますが、うまくいけば、これで正しい道を考えることができます.

于 2010-06-06T21:37:30.743 に答える
2

このようなアルゴリズムを扱うときは、頭の中で問題を小さなチャンクに分割することで利益が得られることがよくあります。

文字列を解析しているので、文字ごとに解決策を検討してください。さらに、これらの文字列の実際のサイズを制御できないため、常に文字列の最初の文字のみを考慮するように制限してください。（まあ - 1つの例外を除いて）

扱っている文字が残りの文字列をさらに調査する必要があると判断したら、それらを捨てます。それらをそのままにしておくと、複雑さが増すだけです。（逆に、文字が完全に一致しない場合は、完了ですよね？）

もちろん、これは文字列の再帰であるため、文字列の全体的な状態を処理する失敗/成功を制御するいくつかの条件が必要です-しかし、それらは問題の本質ではありません-状態を確認してください関数の先頭にある文字列、次に進みます。

完全な解決策が必要な場合に投稿できる、私が作成したアルゴリズム (11 行のコードと中括弧) があります。

于 2010-06-06T22:13:58.443 に答える
2

C# で記述されたサンプル ソリューションを次に示します。コメントが不足して申し訳ありませんが、時間がありませんでした :/ 明日もまだコメントが必要な場合は、いくつか書くことができますが、アイデアをつかんでいただければ幸いです。

 public static bool CompareString(string s1, string s2, bool wildCard)
 {
        // Both strings are empty
        if ((s1.Length == 0) && (s2.Length == 0)) return true;

        // Second string is empty and there is wildCard character
        if (s2.Length == 0 && wildCard) return true;

        //First string is empty. Answer will be true only if all characters in second string are *.
        if (s1.Length == 0 && s2.Length > 0 && s2[0] == '*')
        {
            string newS2 = s2.Remove(0, 1);
            return CompareString(s1, newS2, true);
        }

        // One of the strings is empty, and second one is not.
        if (s1.Length * s2.Length == 0) return false;

        if (wildCard)
        {
            string newS1 = s1.Remove(0, 1);
            if (CompareString(newS1,s2,true) || CompareString(newS1,s2,false))
            {
                return true;
            }
        }
        else
        {
            if (s2[0] == '*')
            {
                string newS2 = s2.Remove(0,1);
                if (CompareString(s1,newS2,true) || CompareString(s1,newS2,false))
                {
                    return true;
                }
            }
            else
            {
                if (s1[0] == s2[0])
                {
                    string newS1 = s1.Remove(0,1);
                    string newS2 = s2.Remove(0,1);
                    return CompareString(newS1,newS2,false);
                }
                else
                {
                    return false;
                }
            }
        }
        return false;
    }
于 2010-06-06T21:28:39.047 に答える