वाइल्डकार्ड पैटर्न

Question

के खिलाफ स्ट्रिंग से मेल खाने के लिए रिकर्सिव फ़ंक्शन इसलिए मैं पूरे दिन इस असाइनमेंट को हल करने का प्रयास कर रहा हूं, बस इसे प्राप्त नहीं कर सकता।

निम्नलिखित फ़ंक्शन 2 तारों को स्वीकार करता है, दूसरा (1 नहीं) संभवतः * (तारांकन) युक्त होता है।
एक * एक स्ट्रिंग के लिए एक स्थानापन्न (खाली, 1 वर्ण या अधिक) है, यह कोई प्रकट हो सकते हैं दिखाई देते हैं (केवल s2 में) एक बार, दो बार, अधिक या बिल्कुल नहीं, यह नहीं एक और * (ab**c) के निकट हो सकता है, इसे जांचने की जरूरत है।

public static boolean samePattern(String s1, String s2) 

स्ट्रिंग एक ही पैटर्न के हैं तो यह सच हो जाता है।
यह रिकर्सिव होना चाहिए, किसी भी लूप, स्थिर & वैश्विक चर का उपयोग न करें। स्थानीय चर का उपयोग & विधि ओवरलोडिंग का उपयोग कर सकते हैं। charAt(i), substring(i), substring(i, j), length():

केवल इन तरीकों का उपयोग कर सकते हैं।

उदाहरण:

1: TheExamIsEasy; 2: The*xamIs*y → सच
1: TheExamIsEasy; 2: Th*mIsEasy* → सच
1: TheExamIsEasy; 2: * → सच
1: TheExamIsEasy; 2: TheExamIsEasy → सच
1: TheExamIsEasy; 2: The*IsHard → गलत

मैं कम से s1 की चार के साथ वर्ण की तुलना एक के बाद एक charAt का उपयोग कर जब तक एक तारक का सामना करना पड़ा है, तो जाँच लें कि तारांकन की तुलना द्वारा एक खाली एक है द्वारा लगातार चार (i+1) है की कोशिश की स्थिति i, यदि सही है - के साथ s2 & is1 के काउंटर के रूप में i+1 के साथ रिकर्सन जारी रखें;
यदि गलत है - दोनों के लिए काउंटर के रूप में i+1 के साथ रिकर्सन जारी रखें।
तब तक जारी रखें जब तक कि कोई अन्य तारांकन स्ट्रिंग का न हो या समाप्त न हो जाए।

मुझे पता नहीं, मेरा दिमाग चीजों का ट्रैक खो देता है, ध्यान केंद्रित नहीं कर सकता, पॉइंटर्स/संकेत? क्या मैं सही दिशा में हूं?

इसके अलावा, यह बताया गया है कि बैकट्रैकिंग तकनीक को हल करने के लिए इसका उपयोग किया जाना है।

मेरे कोड अब तक (काम नहीं करता है, यहां तक ​​कि सैद्धांतिक रूप से):

public static boolean samePattern(String s1, String s2) { 
    if (s1.equals(s2) || s2 == "*") { 
     return true; 
    } 
    return samePattern(s1, s2, 1); 
} 
public static boolean samePattern(String s1, String s2, int i) 
{ 
    if (s1.equals(s2)) 
     return true; 
    if (i == s2.length() - 1) // No *'s found -- not same pattern. 
     return false; 

    if (s1.substring(0, i).equals(s2.substring(0, i))) 
     samePattern(s1, s2, i+1); 
    else if (s2.charAt(i-1) == '*') 
     samePattern(s1.substring(0, i-1), s2.substring(0, i), 1); // new smaller strings. 
    else 
     samePattern(s1.substring(1), s2, i); 
} 

Answer 1

यहाँ कुछ अजगर "psudocode" मदद मिल सकती है

def samePattern(s1,s2): 
    if s2 == "*" or s1 == s2: return True 
    if s1 == "": return False 
    if s1[0] == s2[0]: return samePattern(s1[1:], s2[1:]) 
    if s2[0] == "*": return samePattern(s1, s2[1:]) or samePattern(s1[1:], s2) 
    return False 

है यहाँ सुझाव के लिए पूछने के लिए कोड में परिवर्तित करने

s[0] = the first character 
s[1:] = the string minus the first character 

Answer 2

यहाँ नमूना समाधान सी # में लिखा है। टिप्पणियों की कमी के लिए खेद है लेकिन मेरे पास समय नहीं था:/यदि आपको कल भी उनकी आवश्यकता होगी तो मैं कुछ लिख सकता हूं, लेकिन मुझे आशा है कि आप इस विचार को पकड़ लेंगे।

public static bool CompareString(string s1, string s2, bool wildCard) 
{ 
     // Both strings are empty 
     if ((s1.Length == 0) && (s2.Length == 0)) return true; 

     // Second string is empty and there is wildCard character 
     if (s2.Length == 0 && wildCard) return true; 

     //First string is empty. Answer will be true only if all characters in second string are *. 
     if (s1.Length == 0 && s2.Length > 0 && s2[0] == '*') 
     { 
      string newS2 = s2.Remove(0, 1); 
      return CompareString(s1, newS2, true); 
     } 

     // One of the strings is empty, and second one is not. 
     if (s1.Length * s2.Length == 0) return false; 

     if (wildCard) 
     { 
      string newS1 = s1.Remove(0, 1); 
      if (CompareString(newS1,s2,true) || CompareString(newS1,s2,false)) 
      { 
       return true; 
      } 
     } 
     else 
     { 
      if (s2[0] == '*') 
      { 
       string newS2 = s2.Remove(0,1); 
       if (CompareString(s1,newS2,true) || CompareString(s1,newS2,false)) 
       { 
        return true; 
       } 
      } 
      else 
      { 
       if (s1[0] == s2[0]) 
       { 
        string newS1 = s1.Remove(0,1); 
        string newS2 = s2.Remove(0,1); 
        return CompareString(newS1,newS2,false); 
       } 
       else 
       { 
        return false; 
       } 
      } 
     } 
     return false; 
    } 

Answer 3

अपने वर्तमान दृष्टिकोण के साथ समस्या यह है कि यह सब संभव सबस्ट्रिंग है कि एक * मिलान कर सकते हैं पर विचार नहीं करता है। उदाहरण के लिए, एक ही पैटर्न ("अबाबाबाब", "ए * बी") सच होना चाहिए; * स्ट्रिंग के पहले और अंतिम अक्षर के अलावा सभी से मेल खा सकता है, लेकिन आपका कोड मानता है कि चूंकि निम्न अक्षर बी है, * खाली स्ट्रिंग से मेल खाता है।

मैं सुझाव देता हूं कि उसी दो इनपुट को अपने दो इनपुट तारों को "उपभोग करने" के रूप में सोचने के लिए एक मैच की तलाश है। प्रत्येक चरण में, उसी पैटर्न को केवल प्रत्येक स्ट्रिंग के पहले अक्षर को देखने की आवश्यकता होती है कि यह तय करने के लिए कि पहले वर्ण पर संभव है, और यदि ऐसा है तो बाकी स्ट्रिंग को जांचने के लिए रिकर्सिव कॉल करें। यह चाल जानती है कि पैटर्न स्ट्रिंग में * * तक पहुंचने पर क्या करना है, क्योंकि यह एस 1 में पहले वर्ण से मेल खाने के लिए उपयोग किया जा सकता है या नहीं। क्या करना है यह तय करने के लिए आपको बाकी स्ट्रिंग को देखने की आवश्यकता नहीं है।

चूंकि यह होमवर्क है, इसलिए मैं आपको बताता हूं कि आपके साथ क्या होता है, लेकिन उम्मीद है कि यह आपको सही रास्ते पर सोचने लगेगा।

Answer 4

इस तरह के एल्गोरिदम से निपटने पर, यह अक्सर आपके सिर में छोटे टुकड़ों में समस्या को तोड़ने का भुगतान करता है।

चूंकि आप स्ट्रिंग पार्सिंग कर रहे हैं, तो चरित्र-दर-चरित्र आधार पर समाधान पर विचार करें। इसके अलावा, चूंकि आपके पास इन तारों के वास्तविक आकार पर कोई नियंत्रण नहीं है, इसलिए किसी भी समय स्ट्रिंग के केवल पहले वर्ण पर विचार करने के लिए स्वयं को बाध्य करें। (अच्छी तरह से - एक अपवाद के साथ)

एक बार जब आप निर्धारित किया है कि वे वर्ण जो आप वारंट स्ट्रिंग के शेष भागों में आगे की जांच पड़ताल के साथ काम कर रहे हैं, उन्हें दूर टॉस; उन्हें केवल जटिलता जोड़ते हुए रखते हैं, तो परेशान क्यों? (इसके विपरीत, यदि वर्ण विसंगति से बाहर निकलते हैं, तो आप कर रहे हैं - सही?)

बेशक, यह तारों पर एक पुनरावर्तन है, इसलिए आपको विफलता/सफलता को नियंत्रित करने वाली कुछ स्थितियों को पूरा करना होगा तारों की समग्र स्थिति - लेकिन वे समस्या का मांस नहीं हैं - अपने कार्य के शीर्ष पर स्ट्रिंग की स्थिति की जांच करें, और आगे बढ़ें।

मेरे पास एक एल्गोरिदम है जिसे मैंने व्हीप्ड किया है (कोड की 11 लाइनें, प्लस ब्रेसिज़) जो कि अगर आप एक पूर्ण समाधान चाहते हैं तो मैं पोस्ट कर सकता हूं - लेकिन अगर आप एल्गोरिदम देना चाहते हैं तो मुझे आपके संदेश से यकीन नहीं था, या सिर्फ पॉइंटर्स।