해결 문자열 감소 알고리즘

Question

월요일에 인터뷰를 준비하고 있는데이 문제를 해결하기 위해 "String Reduction"을 발견했습니다. 문제는 다음과 같이 언급한다 :

는, b와 c의 구성된 문자열을 감안할 때, 우리는 다음과 같은 작업을 수행 할 수있는 두 개의 인접한 별개의 문자를 가지고 세 번째 문자로 를 교체하십시오. 예를 들어 'a'와 'c'가 인접한 경우 'b'로 바꿀 수 있습니다. 이 작업을 반복적으로 적용하여 결과가 일 수있는 가장 작은 문자열은 무엇입니까? 예컨대

, 캡 -> CC 또는 캡 -> BB이 하나 2 길이 문자열 초래 한 최적의 솔루션이다 bcab -> AAB -> AC -> B. 더 이상 작업이 적용되지 않으며 결과 문자열은 문자열 = CCCCC의 경우, 작업을 수행 할 수 없습니다 그래서 대답은 5

I에 유래에 많은 questions and answers을 보았다

있지만 길이 1 을 가지고 할 수있다 내 자신의 알고리즘을 확인하고 싶습니다. 다음은 의사 코드의 알고리즘입니다. 내 코드

1. 에서 S 내 문자열 인덱스
2. S [I]는 문자를 줄이기 위해 I
3. P는 스택이다

4. REDUX가 문자를 감소시키는 함수이다. 스택 P의 모든 동작은 O (1)에 있으므로

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

내 알고리즘 최악은 O (N)이다. 위의 예제에서이 알고리즘을 사용해 보았는데 예상되는 대답을 얻었습니다. 날이 예 "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 코드를 작성했습니다. 시스템에 코드를 제출할 때 잘못된 대답이 나타납니다. 나는 당신이 그것을 볼 수 있도록 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 

길이의 새 문자열 N-1은있을 것이다-2 N 쌍과 유사하게 새 길이의 문자열 N-2를해야합니다 n-3 쌍. 이 방법을 적용하는 동안

유지 최소 값을 저장

if (new_min < min) 
    min = new_min 

구현 : 문자열을 줄일 수있는 하나 개 이상의 방법이 있다면 그것은 작은 문자열을 요구하고있다 http://justprogrammng.blogspot.com/2012/06/interviewstreet-challenge-string.html