Решение алгоритма сокращения строк

Question

Я готовлюсь к собеседованию, которое у меня есть в понедельник, и я нашел эту проблему для разрешения «String Reduction». Задача формулируются следующим образом:

Учитывая строку, состоящую из а, Ь и с, мы можем выполнить следующую операцию : Возьмите любые два смежных различные символы и заменить его с третьим символом. Например, если «a» и «c» смежны, они могут быть заменены на «b». Что представляет собой наименьшая строка, которая может получить результат , применяя эту операцию повторно?

Например, кабины -> cc или кабины -> bb, что приводит к веревке длины 2. Для этого одним из оптимальных решений является: bcab -> aab -> ac -> b. Больше никаких действий не могут быть применены и результирующая строка имеет длину 1. Если строка = CCCCC, никакие операции не могут быть выполнены и поэтому ответ 5.

Я видел много questions and answers на StackOverflow, но Я хотел бы проверить свой собственный алгоритм. Вот мой алгоритм в псевдокоде. В моем коде

1. S моя строка уменьшить
2. S [I] является символ с индексом я
3. P является стек:

4. перевождь это функция, которая уменьшает символы.

   function reduction(S[1..n]){   
   P = create_empty_stack(); 
   for i = 1 to n 
   do 
       car = S[i]; 
       while (notEmpty(P)) 
       do 
        head = peek(p); 
        if(head == car) break; 
        else { 
        popped = pop(P); 
        car = redux (car, popped); 
        } 
       done 
       push(car) 
   done 
   return size(P)} 
   

Наихудший моих алгоритмов представляет собой О (п), так как все операции на стеке P на O (1). Я пробовал этот алгоритм в приведенных выше примерах, я получаю ожидаемые ответы. Позвольте мне выполнить мой Algo с этим примером «abacbcaa»:

i = 1 : 
    car = S[i] = a, P = {∅} 
    P is empty, P = P U {car} -> P = {a} 

i = 2 : 
    car = S[i] = b, P = {a} 
    P is not empty : 
     head = a 
     head != car -> 
      popped = Pop(P) = a 
      car = reduction (car, popped) = reduction (a,b) = c 
      P = {∅} 

    push(car, P) -> P = {c} 



i = 3 : 
    car = S[i] = a, P = {c} 
    P is not empty : 
     head = c 
     head != car -> 
      popped = Pop(P) = c 
      car = reduction (car, popped) = reduction (a,c) = b 
      P = {∅} 

    push(car, P) -> P = {b} 


... 


i = 5 : (interesting case) 
    car = S[i] = c, P = {c} 
    P is not empty : 
     head = c 
     head == car -> break 

    push(car, P) -> P = {c, c} 


i = 6 : 
    car = S[i] = b, P = {c, c} 
    P is not empty : 
     head = c 
     head != car -> 
      popped = Pop(P) = c 
      car = reduction (car, popped) = reduction (b,c) = a 
      P = {c} 

    P is not empty : // (note in this case car = a) 
     head = c 
     head != car -> 
      popped = Pop(P) = c 
      car = reduction (car, popped) = reduction (a,c) = b 
      P = {∅} 
    push(car, P) -> P = {b} 

... and it continues until n 

Я запустить этот алгоритм на различных примерах, как это, кажется, работает. Я написал код на Java, который проверяет этот алгоритм, когда я отправляю свой код в систему, я получаю неправильные ответы. Я разместил код java на gisthub, чтобы вы могли его увидеть.

Может кто-нибудь сказать мне, что не так с моим алгоритмом.

Answer 1

Я попытаюсь объяснить, что означает nhahtdh. Существует несколько причин, по которым ваш алгоритм терпит неудачу. Но наиболее фундаментальным является то, что в каждый момент времени только первый наблюдаемый персонаж имеет шанс попасть в стек p. Это не должно быть так, так как вы можете начать сокращение в основном из любой позиции.

Позвольте мне привести строку abcc.Если я контрольную точку в

car = S[i]; 

алго бежать как:

p = {∅}, s = _abcc //underscore is the position 
p = {a}, s = a_bcc 
p = {c}, s = ab_cc 

На данный момент вы застряли с уменьшением ccc

Но есть еще одно сокращение: abcc -> aac ->ab ->c

Кроме того, возврат размера стека P неверен. cc не может быть уменьшен, но алгоритм вернет 1. Вы также должны подсчитать количество пропусков.

Answer 2

вы также можете решить этот вопрос с помощью грубой силы ... и рекурсии

for all n-1 pairs(2 char) replace it with 3rd char if possible and apply reduce on this new string of length n-1 
    for all n-2 pairs replace it with 3rd char and apply reduce on new string 
     for all n-3 pairs....and so on 

Новая строка длины п-1 будет иметь N 2-пары и аналогичным образом новую строку длины N-2 будет иметь n-3 пары.

при применении этого подхода держать хранение минимального значения

if (new_min < min) 
    min = new_min 

Реализация: http://justprogrammng.blogspot.com/2012/06/interviewstreet-challenge-string.html