जांचें कि क्या स्ट्रिंग में वर्ण O(1) में एक पालिंड्रोम बनाते हैं पायथन में अतिरिक्त स्थान

मान लीजिए कि हमारे पास एक स्ट्रिंग s है। इस स्ट्रिंग में लोअरकेस वर्ण, अन्य विशेष वर्ण और संख्याएँ हो सकती हैं। हमें यह जांचना है कि क्या केवल स्ट्रिंग में मौजूद अक्षर पैलिंड्रोमिक हैं या नहीं। यहाँ एक बाधा यह है कि वहाँ हमें इस समस्या को हल करने के लिए अतिरिक्त स्थान का उपयोग करने की अनुमति नहीं है।

इसलिए, यदि इनपुट s ="ra$5ce58car" जैसा है, तो आउटपुट ट्रू होगा, क्योंकि अक्षर "रेसकार" बना रहे हैं जो पैलिंड्रोम है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

फ़ंक्शन को परिभाषित करें first_letter_index() । यह स्ट्र, लेफ्ट, राइट लेगा
सूचकांक :=-1
मैं के लिए बाएं से दाएं + 1 की सीमा में, करो
- अगर str[i] लोअर केस अल्फाबेट है, तो
  - सूचकांक:=मैं
  - लूप से बाहर आएं
रिटर्न इंडेक्स
एक फ़ंक्शन को परिभाषित करें last_letter_index() । यह स्ट्र, लेफ्ट, राइट लेगा
सूचकांक :=-1
मैं के लिए बाएं से दाएं -1 की सीमा में, 1 से घटाएं
- अगर str[i] लोअर केस अल्फाबेट है, तो
  - सूचकांक:=मैं
  - लूप से बाहर आएं
- रिटर्न इंडेक्स
- मुख्य विधि से निम्न कार्य करें:
- बाएं:=0, दाएं:=str-1 का आकार
- झंडा :=सच
- मैं के लिए 0 से लेकर स्ट्र के आकार तक के लिए, करें
  - बाएं:=first_letter_index(str, बाएं, दाएं)
  - दाएं:=last_letter_index(str, दाएँ, बाएँ)
  - यदि दाएं <0 या बाएं <0, तो
    - लूप से बाहर आएं
  - यदि str[बाएं] str[दाएं] के समान है, तो
    - बाएं:=बाएं + 1
    - दाएं:=दाएं - 1
    - अगले पुनरावृत्ति के लिए जाएं
  - झंडा :=झूठा
    - लूप से बाहर आएं
वापसी का झंडा

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण कोड

def first_letter_index(str, left, right):
   index = -1
   for i in range(left, right + 1):
      if str[i] >= 'a' and str[i] <= 'z' :
         index = i
         break
 
   return index

def last_letter_index(str, left, right):
   index = -1
   for i in range(left, right - 1, -1) :
      if str[i] >= 'a' and str[i] <= 'z':
         index = i
         break
 
   return index

def solve(str):
   left = 0
   right = len(str) - 1
   flag = True
 
   for i in range(len(str)) :
      left = first_letter_index(str, left, right)
      right = last_letter_index(str, right, left)
 
      if right < 0 or left < 0:
         break
      if str[left] == str[right]:
         left += 1
         right -= 1
         continue
 
      flag = False
      break
 
   return flag
 
s = "ra$5ce58car"
print(solve(s))

इनपुट

"ra$5ce58car"

आउटपुट

True