Поиск минимальной строки, удовлетворяющей некоторым условиям

Question

Недавно во время собеседования мне была задана следующая проблема.

Учитывая строку S, мне нужно найти другую строку S2 такую, что S2 является подпоследовательностью S, а также S является подпоследовательностью S2 + reverse (S2). Здесь '+' означает конкатенацию. Мне нужно вывести минимальную длину S2 для заданного S.

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

Edit-

Есть ли способ сделать это в O (N 2 ) или меньше.

Answer 1

Каждый символ из S может быть включен в S2 или нет. При том, что мы можем построить рекурсию, пытающуюся два случая:

• первого символ S используется для покрытия,
• первого символа S не используется для покрытия,

и вычислить минимум эти две крышки. Чтобы реализовать это, достаточно проследить, сколько S покрыто уже выбранным S2 + обратным (S2).

Есть оптимизация, когда мы знаем, какой результат (найденная обложка, не может иметь обложку), и не нужно брать первый символ для обложки, если он не будет покрывать что-то.

Простая реализация питон:

cache = {} 

def S2(S, to_cover): 
    if not to_cover: # Covered 
     return '' 
    if not S:   # Not covered 
     return None 
    if len(to_cover) > 2*len(S): # Can't cover 
     return None 
    key = (S, to_cover) 
    if key not in cache: 
     without_char = S2(S[1:], to_cover)  # Calculate with first character skipped 
     cache[key] = without_char 
     _f = to_cover[0] == S[0] 
     _l = to_cover[-1] == S[0] 
     if _f or _l: 
      # Calculate with first character used 
      with_char = S2(S[1:], to_cover[int(_f):len(to_cover)-int(_l)]) 
      if with_char is not None: 
       with_char = S[0] + with_char # Append char to result 
       if without_char is None or len(with_char) <= len(without_char): 
        cache[key] = with_char 
    return cache[key] 

s = '21211233123123213213131212122111312113221122132121221212321212112121321212121132' 
c = S2(s, s) 
print len(s), s 
print len(c), c 

Answer 2

Допустим, что S2 является "яблоко". Тогда мы можем сделать такое предположение:

S2 + reverseS2> = S> = S2
"appleelppa"> = S> = "яблоко"

So данный S будет что-то, в том числе «яблоко», не более, чем «appleelppe». Это может быть «appleel» или «appleelpp».

String S ="locomotiffitomoc"; 
// as you see S2 string is "locomotif" but 
// we don't know S2 yet, so it's blank 
String S2 = ""; 
for (int a=0; a<S.length(); a++) { 
    try { 
     int b = 0; 
     while (S.charAt(a - b) == S.charAt(a + b + 1)) 
      b++; 
     // if this for loop breaks that means that there is a character that doesn't match the rule 
     // if for loop doesn't break but throws an exception we found it. 
    } catch (Exception e) { 
     // if StringOutOfBoundsException is thrown this means end of the string. 
     // you can check this manually of course. 
     S2 = S.substring(0,a+1); 
     break; 
    } 
} 
System.out.println(S2); // will print out "locomotif" 

Поздравляем, вы нашли минимум S2.

Answer 3

В этой проблеме есть два важных аспекта.

1. Так как нам нужно S в качестве подстроки S2 + обратное (S2), S2, должны иметь по крайней мере N/2 длины.
2. После конкатенации S2 и обратного (S2) есть образец, где алфавиты повторяет, такие как

Таким образом, решение, чтобы проверить от центра S до конца S для любых последовательных элементов.Если вы найдете его, проверьте элементы с обеих сторон, как показано на рисунке.

Теперь, если вы в состоянии достигнуть до конца строки, то минимальное количество элементов (результат) расстояние от начала до точки, где вы найдете последовательные элементы. В этом примере его C i.e 3.

Мы знаем, что это может случиться не всегда. т. е. вы не сможете найти последовательные элементы в центре. Скажем, последовательные элементы после центра, то мы можем сделать тот же тест.

Главная строка

Substring

каскадных строка

Теперь прибывает т он сильно сомневается. Почему мы рассматриваем только левую сторону, начиная с центра? Ответ прост, конкатенированная строка выполняется с помощью S + reverse (S). Таким образом, мы уверены, что последний элемент в подстроке происходит последовательно в конкатенированной строке. Нет никакого способа, чтобы любое повторение в первой половине основной строки могло дать лучший результат, потому что по крайней мере у нас должны быть n алфавитов в конечной конкатенированной строке

Теперь вопрос сложности: Поиск последовательных алфавитов дает максимум O (n) Теперь проверка элементов с обеих сторон итерационно может дать худшую сложность O (n). максимальные n/2 сравнения. Мы можем терпеть неудачу много раз, выполняя вторую проверку, так что у нас есть мультипликативная связь между сложностями i.e O (n * n).

Я считаю, что это правильное решение и еще не нашло лазейки.