वैध पलिंद्रोम  


कठिनाई स्तर आसान
में अक्सर पूछा इंफोसिस MAQ नोकिया ओ 9 के समाधान
तार दो सूचक

एक दिया गया स्ट्रिंग s की लंबाई n। यह पता लगाने के लिए एक कार्यक्रम लिखें कि क्या स्ट्रिंग वैध है या नहीं। यदि नहीं, तो आप इसे एक तालमेल बनाने के लिए स्ट्रिंग के अधिकांश एक वर्ण से हटा सकते हैं।

कोई भी तार जो उल्टा होता है, उसे पलिंद के रूप में जाना जाता है।

उदाहरण के लिए:

  1. स्ट्रिंग = "नाइटिन" और रिवर्स स्ट्रिंग = "नाइटिन" जो समान हैं इसलिए यह एक पैलिंड्रोम है।
  2. string = "apple" और रिवर्स स्ट्रिंग = "elppa" जो समान नहीं हैं इसलिए यह एक palindrome नहीं है।

वैध पलिंद्रोमपिन

उदाहरण  

इनपुट: s = "abcdba"

आउटपुट: हां ('सी' या 'डी' को हटाकर)

इनपुट: s = "अब्बा"

आउटपुट: हाँ (पहले से ही एक palindrome)

इनपुट: s = "नीला"

आउटपुट: नहीं

मान्य Palindrome के लिए एल्गोरिथ्म  

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

  1. एक स्ट्रिंग प्रारंभ करें।
  2. शुरुआती इंडेक्स का उपयोग करके और इंडेक्स पॉइंटर को समाप्त करने के लिए ट्रैवर्सिंग शुरू करें।
  3. जाँच करें कि क्या दोनों अनुक्रमितों पर वर्ण सूचक को प्रारंभ करने और सूचक को समाप्त करने के लिए समान वेतन वृद्धि है। यदि इंडेक्स शुरू करना इंडेक्स रिटर्न को समाप्त करने से अधिक या उसके बराबर है।
  4. इनमें से किसी एक पात्र को हटाकर ऐलिस पैलेंड्रोम बनाने की कोशिश करें।
  5. यदि पैलिंड्रोम में इंडेक्स परिणाम शुरू करने पर चरित्र को हटा दें तो यह सही है।
  6. सही है अगर पैलिंड्रोम में इंडेक्स परिणामों को समाप्त करने वाले चरित्र को हटा दें तो यह सही है।
  7. झूठे झूठे।

C ++ प्रोग्राम Valid Palindrome की जाँच करने के लिए  

#include <bits/stdc++.h> 
using namespace std; 

bool isPalindrome(string::iterator low, string::iterator high){ 
    while(low < high){ 
       if(*low != *high) 
          return false; 
       low++; 
       high--; 
    } 
    return true; 
} 
  
bool Palindrome(string s){ 
    int low = 0, high = s.length() - 1; 
  
    while(low < high){ 
        if(s[low] == s[high]){ 
            low++; 
            high--; 
        } 
        else{ 
            if(isPalindrome(s.begin() + low + 1, s.begin() + high)) 
                return true; 
  
            if (isPalindrome(s.begin() + low, s.begin() + high - 1)) 
                return true; 
  
            return false; 
        } 
    } 
  
    return true; 
} 
  
int main(){ 
    string s = "abcdba"; 
    
    if(Palindrome(s)){
        cout<<"Yes";
    } 
    else{
        cout<<"No";
    }
    return 0; 
}
Yes

Valid Palindrome की जाँच करने के लिए जावा प्रोग्राम  

import java.util.*; 
  
class validPalindrome{ 
  
    static boolean isPalindrome(String s, int low, int high){ 
        while(low < high){ 
            if(s.charAt(low) != s.charAt(high)) 
                return false; 
            low++; 
            high--; 
        } 
        return true; 
    } 
  
    static boolean Palindrome(String s){ 
  
        int low = 0, high = s.length() - 1; 
  
        while(low < high){ 
  
            if(s.charAt(low) == s.charAt(high)){ 
                low++; 
                high--; 
            }  
            else{ 
  
                if(isPalindrome(s, low + 1, high)) 
                    return true; 
  
                if(isPalindrome(s, low, high - 1)) 
                    return true; 
                return false; 
            } 
        } 
  
        return true; 
    } 
  
    public static void main(String[] args){ 
        String s = "abcdba"; 
        
        if(Palindrome(s)){
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
    } 
} 
Yes

जटिलता विश्लेषण  

समय जटिलता

पर)  जहाँ n दी गई स्ट्रिंग की लंबाई है।

यह भी देखें
सिर सूचक के बिना लिंक की गई सूची से एक नोड हटाएं

सहायक स्थान

ओ (1) क्योंकि हम यहाँ किसी अतिरिक्त स्थान का उपयोग नहीं करते हैं।

refrences