文字列をワイルドカードパターンと一致させる再帰関数

Question

ですから、私はこの課題を一日中解決しようとしてきましたが、それを手に入れることができません。

次の関数は2つの文字列を受け入れます。 *'（アスタリスク）。
an * 文字列（空、1枚以上）の代替品であり、表示される可能性があります（S2でのみ）2回、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 →true
1: TheExamIsEasy; 2: Th*mIsEasy* →true
1: TheExamIsEasy; 2: * →true
1: TheExamIsEasy; 2: TheExamIsEasy →true
1: TheExamIsEasy; 2: The*IsHard →FALSE

Charsを1つずつ使用して比較してみました charAt アスタリスクに遭遇するまで、アスタリスクが空のアスタリスクであるかどうかを確認して、連続したchar（i+1）charで s1 位置に i, 、真実の場合 - 再帰を続けます i+1 カウンターとして s2 & i カウンターとして s1;
偽の場合 - 再帰を続けます i+1 両方のカウンターとして。
別のアスタリスクが見つかるか、文字列の終わりが見つかるまでこれを続けます。

私は知らない、私の脳は物事のトラックを失い、集中できない、 ポインター /ヒント？私は正しい方向にいますか？

また、a バックトラッキング テクニックはこれを解決するために使用されます。

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

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

Answer 1

これが役立つかもしれないPythonの「psudocode」です

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

Answer 2

現在のアプローチの問題は、A *が一致する可能性のあるすべてのサブストリングを考慮していないことです。たとえば、samepattern（ "ababababab"、 "a*b"）はtrueを返す必要があります。 *は文字列の最初と最後の文字を除くすべてに一致させることができますが、あなたのコードは、次の文字はbであるため、 *は空の文字列と一致すると想定しています。

Samepatternは、マッチを探しているときに2つの入力文字列を「消費」すると考えることをお勧めします。各ステップで、samepatternは各文字列の最初の文字を見るだけで、一致するかどうかを決定する必要があります 最初のキャラクターで 可能であり、もしそうなら、文字列の残りの部分をチェックするために再帰的な呼び出しを行います。トリックは、S1の最初の文字と一致するために使用される場合と使用できない場合があるため、パターン文字列の *に到達したときに何をすべきかを知ることです。何をすべきかを決定するために、文字列の残りの部分を見る必要はありません。

これは宿題なので、私はあなたに何が起こるかの詳細を理解しておきますが、うまくいけば、これがあなたが正しい道を考えているでしょう。

Answer 3

これは、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;
    }

Answer 4

このようなアルゴリズムを扱うとき、それはしばしばあなたの頭の中の小さな塊に問題を打ち破ることを支払うでしょう。

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

あなたが扱っているキャラクターが文字列の残りの部分をさらに調査することを保証すると判断したら、 それらを捨ててください;それらを維持することは複雑さだけを追加するだけなので、なぜわざわざなのですか？ （逆に、キャラクターが不一致をフラットにする場合、あなたは完了です - 正しく？）

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

完全な解決策が必要な場合に投稿できるアルゴリズム（コードの11行とブレース）がありますが、アルゴリズムを与えたいか、ポインターを与えたいかどうかはあなたのメッセージではわかりませんでした。