स्ट्रिंग कमी को हल करना एल्गोरिदम

Question

मैं अपने आप को एक साक्षात्कार के लिए तैयार कर रहा हूं जो मेरे पास सोमवार को है और मुझे यह समस्या "" नामक हल करने के लिए मिली है। समस्या इस तरह कहा गया है:

एक, बी और सी के से मिलकर एक स्ट्रिंग को देखते हुए, हम निम्नलिखित आपरेशन प्रदर्शन कर सकते हैं: किसी भी दो आसन्न अलग पात्रों ले लो और यह तीसरे चरित्र के साथ बदलें । उदाहरण के लिए, यदि 'ए' और 'सी' आसन्न हैं, वे 'बी' के साथ प्रतिस्थापित कर सकते हैं। इस ऑपरेशन को बार-बार लागू करके परिणाम सबसे छोटी स्ट्रिंग क्या है?

उदाहरण के लिए, कैब -> सीसी या कैब -> बीबी, जिसके परिणामस्वरूप की एक स्ट्रिंग होती है 2. इसके लिए, एक इष्टतम समाधान है: bcab -> aab -> ac -> b। कोई और अधिक आपरेशन लागू किया जा सकता है और उसके एवज में स्ट्रिंग की लंबाई 1. है स्ट्रिंग = CCCCC है, तो कोई संचालन किया जा सकता है और इतने जवाब 5.

मैं stackoverflow पर एक बहुत questions and answers देखा है लेकिन है मैं अपना खुद का एल्गोरिदम सत्यापित करना चाहता हूं। छद्म कोड में मेरा एल्गोरिदम यहां है। मेरी कोड

1. में एस मेरी स्ट्रिंग सूचकांक पर
2. एस [i] है चरित्र को कम करना है मैं
3. पी एक ढेर है:

4. redux समारोह है कि पात्रों को कम कर देता है।

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

मेरी एल्गोरिदम के बुरी से बुरी हालत हे (एन) है, क्योंकि सब ढेर पी पर कार्रवाई हे (1) पर है। मैंने ऊपर दिए गए उदाहरणों में इस एल्गोरिदम की कोशिश की, मुझे अपेक्षित उत्तर मिलते हैं। मुझे इस उदाहरण "abacbcaa" के साथ मेरी algo पर अमल करते हैं:

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 

मैं इस तरह विभिन्न उदाहरणों पर इस एल्गोरिथ्म चलने के बाद, यह काम करने लगता है। मैंने जावा में एक कोड लिखा है जो इस एल्गोरिदम का परीक्षण करता है, जब मैं सिस्टम में अपना कोड जमा करता हूं, तो मुझे गलत जवाब मिल रहे हैं। मैंने जावा कोड को gisthub पर पोस्ट किया है ताकि आप इसे देख सकें।

क्या कोई मुझे बता सकता है कि मेरे एल्गोरिदम के साथ क्या गलत है।

Answer 1

मैं nhahtdh का अर्थ समझाने की कोशिश करने जा रहा हूं। आपके एल्गोरिदम विफल होने के कई कारण हैं। लेकिन सबसे मौलिक बात यह है कि समय पर प्रत्येक बिंदु पर, केवल पहले वर्ण को देखा गया है, जो स्टैक p पर धकेलने का मौका है। यह इस तरह से नहीं होना चाहिए, क्योंकि आप किसी भी स्थिति से मूल रूप से कमी शुरू कर सकते हैं।

मुझे आपको स्ट्रिंग abcc देने दें।अगर मैं

car = S[i]; 

पर ब्रेकपाइंट के रूप में algo रन: यदि आप एक कमी ccc

साथ फंस रहे हैं लेकिन वहाँ एक और कमी है

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

इस बिंदु पर: 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-2 ही होगी एन -3 जोड़े

जबकि इस दृष्टिकोण को लागू न्यूनतम मूल्य भंडारण रखने

if (new_min < min) 
    min = new_min 

कार्यान्वयन: http://justprogrammng.blogspot.com/2012/06/interviewstreet-challenge-string.html