यह पता लगाना कि कोई स्ट्रिंग एक निश्चित पैटर्न

Question

से मिलती है, मैंने हाल ही में Google के साथ सॉफ़्टवेयर इंजीनियरिंग की स्थिति के लिए एक साक्षात्कार लिया था और सवाल एक पैटर्न मैचर बनाने के संबंध में पूछा गया था।

a) 'a'-'z' chars 
b) '*' chars which can be matched by 0 or more letters 
c) '?' which just matches to a character - any letter basically 

तो कॉल

की तरह कुछ हो सकता है:

givenPattern एक स्ट्रिंग है शामिल है:

तो तुम जो निम्न करता

boolean isPattern(String givenPattern, String stringToMatch) 

समारोह का निर्माण करने के लिए है

isPattern("abc", "abcd") - झूठी वापसी करता है क्योंकि यह डी ओ इ एस आकार से मिलान नहीं ('प' अतिरिक्त है)

isPattern("a*bc", "aksakwjahwhajahbcdbc") है, जो सच है के रूप में हम एक 'एक' शुरू में, कई पात्रों के बाद और फिर इसे "ई.पू."

isPattern("a?bc", "adbc") रिटर्न सच के साथ समाप्त होता है जैसा कि पैटर्न के प्रत्येक चरित्र दिए गए स्ट्रिंग में मेल खाता है।

साक्षात्कार के दौरान, समय छोटा होने पर, मुझे लगा कि कोई पैटर्न के माध्यम से चल सकता है, देखें कि कोई चरित्र एक पत्र है, एक * या एक? और उसके बाद क्रमशः दिए गए स्ट्रिंग में वर्णों से मेल खाते हैं। लेकिन यह फॉर-लूप का एक जटिल सेट बन गया और हमने 45 मिनट के भीतर एक निष्कर्ष निकालने का प्रबंधन नहीं किया।

क्या कोई मुझे बता सकता है कि वे इस समस्या को जल्दी और कुशलता से कैसे हल करेंगे?

बहुत धन्यवाद!

Answer 1

boolean isPattern(String givenPattern, String stringToMatch) { 
    if (givenPattern.empty) 
     return stringToMatch.isEmpty(); 
    char patternCh = givenPatter.charAt(0); 
    boolean atEnd = stringToMatch.isEmpty(); 
    if (patternCh == '*') { 
     return isPattenn(givenPattern.substring(1), stringToMatch) 
      || (!atEnd && isPattern(givenPattern, stringToMatch.substring(1))); 
    } else if (patternCh == '?') { 
     return !atEnd && isPattern(givenPattern.substring(1), 
      stringToMatch.substring(1)); 
    } 
    return !atEnd && patternCh == stringToMatch.charAt(0) 
      && isPattern(givenPattern.substring(1), stringToNatch.subtring(1); 
} 

(Recursion को समझने के लिए सबसे आसान है।)

Answer 2

मान लें आप regexes उपयोग करने के लिए अनुमति दी जाती है, तो आप की तरह कुछ लिख सकता:

static boolean isPattern(String givenPattern, String stringToMatch) { 
    String regex = "^" + givenPattern.replace("*", ".*").replace("?", ".") + "$"; 

    return Pattern.compile(regex).matcher(stringToMatch).matches(); 
} 

"^" स्ट्रिंग
"$" की शुरुआत है स्ट्रिंग के अंत
. "किसी भी चरित्र के लिए है ", ठीक उसी बार
.*" किसी भी चरित्र ", 0 या अधिक बार

नोट: यदि आपको प्रतिबंधित करना चाहते हैंऔर ? केवल अक्षरों के लिए, आप . के बजाय [a-zA-Z] का उपयोग कर सकते हैं।