Проверьте, является ли строка C чередованием A и B

Учитывая три строки A, B и C. Напишите функцию, которая проверяет, является ли C чередованием A и B. C называется чередованием A и B, если он содержит все символы A и B и порядок всех символы в отдельных строках сохраняются.

Например:

  • "hotdog" - это чередование "горячих" и "собачьих" (простых)
  • 'superb' - это чередование 'up' и 'serb'
  • "сердечная боль" - это чередование "уха" и "болей".
  • "chat" - это чередование "шляпы" и "кошки"
  • 'cheaters' не является чередованием "чата" и "провидца", потому что, хотя в нем содержатся все буквы от каждого, буквы из "провидца" не отображаются в порядке

Я нахожу некоторые решения в net, но ниже мой подход может кто-нибудь сказать мне, что я что-то упустил или мой алгоритм будет работать?.

Мое Алго:

  • Пройдите через a и c. Во время обхода мы сначала вычисляем две вещи: присутствует ли char или нет и сохраняет индекс i.e. f, где найден char. И как только мы найдем char, в этом месте мы должны поместить некоторые специальные char, чтобы мы не рассматривали этот char далее.
  • Для следующего char в a поиска в c из индекса, где вы нашли предыдущий char i.e. f. если мы не найдем возврата.
  • То же самое можно сделать и для b.
  • Если после выполнения вышеуказанного шага, если мы найдем false, чем повторить для первого b, чем a и вернем результат.

например.

a = xxy, b = xxz and c = xxzxxxy

начните с:

  • для x в a, c = 0xzxxxy (я помещаю 0 как специальный char)
  • для x в a, начинаем с индекса 0 вперед (потому что мы нашли предыдущий char при 0) c = 00zxxxy.
  • для y в a, c = 00zxxx0
  • для x в b, c = 00z0xx0
  • для x в b, c = 00z00x0
  • для z в b, мы не смогли найти z после индекса 4, который был индексом, где мы нашли предыдущий char для b.

начиная с a, возвращает false, поэтому мы начнем с b.

Итак, начните с b:

  • для x в b, c = 0xzxxxy
  • для x в b, c = 00zxxxy
  • для z в b, c = 000xxxy
  • для x в a, c = 0000xxy
  • для x в a, c = 00000xy
  • для y в a, c = 00000x0

следовательно, истина i.e.c является чередующейся строкой a и b.

Ответы

Ответ 1

Ваше решение представляет жадный алгоритм с небольшой модификацией, потому что он считает символ в C как принадлежащий A на первый проход (или на B на втором проходе), как только он найдет совпадение. Это сломается для следующих строк:

A = xxyxxy
B = xxzxxz
C = xxzxxyxxyxxz

Первый проход, который подсчитывает соответствующий символ, как член A, превратит C в

00zxx0000xxz

Второй проход, который считает совпадающий символ в качестве члена B, превратит C в

00000yxxyxx0

Вот простая реализация Java memoized:

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

Демо на идеоне.

Ответ 2

Сначала я проверил бы, что длина A и длина B суммируются равной длине C.

Затем проверьте, равен ли первый символ A первому символу C.

Если нет, проверьте, равен ли первый символ B первому символу C.

Проверьте другие символы, начинающиеся с 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;
}

Вы бы назвали этот метод не более двух раз. Вызовы будут либо

if (isInterleaved(a, b, c))

или

if (isInterleaved(b, a, c))

Если первый символ A и первый символ B равны, проверьте другие символы, начиная с строки A или B, с которой вы не начинали на предыдущем шаге.

Таким образом, вы сохраняете сложное тестирование для строк, которые могут удовлетворять условиям.

Ответ 3

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