11

3 つの文字列 A、B、C が与えられた場合、C が A と B のインターリーブかどうかをチェックする関数を記述します。C が A と B のすべての文字と個々のすべての文字の順序を含む場合、C は A と B のインターリーブであると言われます。文字列は保持されます。

例えば：

  • 'hotdog' は 'hot' と 'dog' のインターリーブです (簡単)
  • 'superb' は 'up' と 'serb' のインターリーブです。
  • 'heartache' は 'ear' と 'ache' のインターリーブです
  • 'chat' は 'hat' と 'cat' のインターリーブです
  • 'cheaters' は'chat' と 'seer' のインターリーブではありません。これは、それぞれの文字がすべて含まれている一方で、'seer' の文字が順番どおりに表示されないためです。

私はネットでいくつかの解決策を見つけましたが、以下は私のアプローチです。ありがとう。

私のアルゴリズム:

  1. とをトラバースしaますc。トラバーサル中、最初に 2 つのことを計算します: char が存在するかどうかと、インデックス、つまりfchar が見つかった場所を保存します。そして、char を見つけ次第、その場所に特別な char を配置して、この char をそれ以上考慮しないようにする必要があります。
  2. 前の文字を見つけたインデックスから、次の文字をa検索します。見つからない場合は戻ります。cf
  3. あなたも同じですb。
  4. 上記の手順を実行した後、見つかった場合は最初にfalse繰り返して結果を返します。ba

例えば

a = xxy, b = xxz and c = xxzxxxy

から始めます:

  1. for x in a, c = 0xzxxxy (特殊文字として 0 を入れています)
  2. a の x の場合、インデックス 0 以降から開始します (前の文字が 0 で見つかったため)c = 00zxxxy.
  3. a の y の場合、c = 00zxxx0
  4. b の x の場合、c = 00z0xx0
  5. b の x の場合、c = 00z00x0
  6. b の z の場合、b の前の文字を見つけたインデックスであるインデックス 4 の後に z を見つけることができませんでした。

で始まるとafalse が返されるので、ここでbから始めます。

したがって、bから始めます：

  1. b の x の場合、c = 0xzxxxy
  2. b の x の場合、c = 00zxxxy
  3. b の z の場合、c = 000xxxy
  4. a の x の場合、c = 0000xxy
  5. a の x の場合、c = 00000xy
  6. a の y の場合、c = 00000x0

したがって、true iec は a と b のインターリーブされた文字列です。

4

3 に答える 3

9

あなたのソリューションは、一致が見つかるとすぐに最初のパス (または2 番目のパス)に属する文字をカウントするため、わずかな変更を加えた貪欲なアルゴリズムを表しています。これは、次の文字列で壊れます。CAB

A = xxyxxy
B = xxzxxz
C = xxzxxyxxyxxz

のメンバーとして一致する文字をカウントする最初のパスは、Aに変わりCます

00zxx0000xxz

一致する文字をメンバーとしてカウントする 2 番目のパスBはC、

00000yxxyxx0

以下は、メモ化されたソリューションの単純な Java 実装です。

private static boolean checkOverlap(String a, String b, String c) {
    Boolean[][][] memoize = new Boolean[a.length()+1][b.length()+1][c.length()+1];
    return checkOverlap(a, b, c, 0, 0, 0, memoize);
}
private static boolean checkOverlap(
    String a
,   String b
,   String c
,   int pa
,   int pb
,   int pc
,   Boolean[][][] memoize
) {
    Boolean res = memoize[pa][pb][pc];
    if (res != null) {
        return (boolean)res;
    }
    if (pa == a.length() && pb == b.length() && pc == c.length()) {
        res = true;
    } else if (pc == c.length()) {
        res = false;
    } else {
        res = false;
        if (pa != a.length() && c.charAt(pc) == a.charAt(pa) && checkOverlap(a, b, c, pa+1, pb, pc+1, memoize)) {
            res = true;
        } else if (pb != b.length() && c.charAt(pc) == b.charAt(pb) && checkOverlap(a, b, c, pa, pb+1, pc+1, memoize)) {
            res = true;
        }
    }
    return (memoize[pa][pb][pc] = res);
}

ideone のデモ。

于 2013-09-06T18:37:51.557 に答える
0 
def isinterleave(a, b, c):
   la = len(a)
   lb = len(b)
   lc = len(c)
   if la + lb != lc: return False
   if la == lb == lc == 0: return True
   if (la > 0 and lb >0 and a[0] == b[0] == c[0]):
     return isinterleave(a[1:], b, c[1:]) or isinterleave(a, b[1:], c[1:])
   if (la > 0 and a[0] == c[0]):
     return isinterleave(a[1:], b, c[1:])
   if (lb > 0 and b[0] == c[0]):
     return isinterleave(a, b[1:], c[1:])
   return False
于 2013-09-06T19:29:17.737 に答える
0

まず、A の長さと B の長さの合計が C の長さと等しいことを確認します。

次に、A の最初の文字が C の最初の文字と等しいかどうかを確認します。

そうでない場合は、B の最初の文字が C の最初の文字と等しいかどうかを確認します。

上記の 2 つの条件のどちらが真であったかに応じて、A または B で始まる他の文字を確認します。

テストを実行するメソッドは次のとおりです。

public boolean isInterleaved(String a, String b, String c) {
    int aIndex = 0;
    int bIndex = 0;
    int cIndex = 0;
    while (cIndex < c.length()) {
        if (aIndex < a.length()) {
            if (a.charAt(aIndex) != c.charAt(cIndex)) { return false; }
            cIndex++;
            aIndex++;
        }
        if (bIndex < b.length()) { 
            if (b.charAt(bIndex) != c.charAt(cIndex)) { return false; }
            cIndex++;
            bIndex++;
        }
    }

    return true;
}

このメソッドは最大で 2 回呼び出します。呼び出しは次のいずれかになります

if (isInterleaved(a, b, c))

また

if (isInterleaved(b, a, c))

A の最初の文字と B の最初の文字が等しい場合は、前の手順で開始しなかった A または B の文字列で始まる他の文字を確認します。

このようにして、条件を満たす可能性のある文字列の複雑なテストを省略できます。

于 2013-09-06T18:18:01.713 に答える