वैध पलिंड्रोम लेटकोड समाधान


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना सेब ब्लूमबर्ग Facebook माइक्रोसॉफ्ट ओरेकल Wayfair
तार दो संकेत

समस्या का विवरण

एक दिया गया स्ट्रिंग, हमें यह निर्धारित करना होगा कि क्या यह केवल एक वर्णमाला है, केवल वर्णमाला वर्णों यानी संख्याओं और वर्णमालाओं को देखते हुए। हमें वर्णमाला के पात्रों के मामलों को भी अनदेखा करना होगा।

उदाहरण

"A man, a plan, a canal: Panama"
true

स्पष्टीकरण:

"अमानप्लानाकनालपनामा" एक वैध पालि है।

"race a car"
false

स्पष्टीकरण:

"रेसकार" एक पैलेंड्रोम नहीं है।

Naive दृष्टिकोण (रिवर्स के साथ तुलना)

यह जांचने के लिए कि क्या कोई स्ट्रिंग पैलिंड्रोम है या नहीं, हम इसे उल्टा कर सकते हैं और इसकी तुलना मूल स्ट्रिंग से कर सकते हैं। उलटने के बाद अगर यह बराबर रहता है तो दिए गए स्ट्रिंग एक पैलिंड्रोम है।
इस समस्या में हमें अक्षर और संख्या को छोड़कर सभी वर्णों को अनदेखा करना होगा। तो इसके लिए हम दिए गए स्ट्रिंग को फ़िल्टर कर सकते हैं और फ़िल्टर किए गए स्ट्रिंग को सभी अवांछित वर्णों को हटाकर एक नए चर में सहेज सकते हैं। चलो एक उदाहरण लेते हैं:

वैध पलिंड्रोम लेटकोड समाधान

 

 

 

 

हम फ़िल्टर किए गए स्ट्रिंग को देख सकते हैं और उलट फ़िल्टर किया गया स्ट्रिंग बराबर नहीं है, इसलिए यह एक मान्य palindrome नहीं है।

मान्य पलिंड्रोम लेटेकोड समाधान के लिए कार्यान्वयन

C ++ प्रोग्राम

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

bool isAlphaNum(char c)
{
    if( (48<=c && c<=57) || (65<=c && c<=90) || (97<=c && c<=122)) 
        return true;
    return false;
}
    
char lowerCase(char c)
{
    if(65<=c && c<=90)
        return c+32;
    else 
        return c;
}
    
bool isPalindrome(string s) 
{
    string input;

    for(char c:s)
    {
        if(isAlphaNum(c))
            input+= lowerCase(c);
    }

    string reversed=input;
    reverse(reversed.begin(),reversed.end());

    if(input==reversed) return true;
    else return false;

}

int main() 
{
    string s="A man, a plan, a canal: Panama";
    if(isPalindrome(s))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

  return 0; 
}
true

जावा प्रोग्राम

import java.lang.*;

class Rextester
{  
    static boolean isAlphaNum(char c)
    {
        if( (48<=c && c<=57) || (65<=c && c<=90) || (97<=c && c<=122)) 
            return true;
        else
            return false;
    }
    
    static char lowerCase(char c)
    {
        if(65<=c && c<=90)
            return (char)(c+32);
        else 
            return c;
    }
    
    public static boolean isPalindrome(String s) 
    {
       StringBuffer buf= new StringBuffer();
        
       for(char c: s.toCharArray())
       {
           if(isAlphaNum(c))
               buf.append(lowerCase(c));
       }
        
        String input,reversed;
        input= buf.toString();
        reversed= buf.reverse().toString();
        
        if(input.equals(reversed))
            return true;
        else 
            return false;
        
    }
    
    public static void main(String args[])
    {
       String s="A man, a plan, a canal: Panama";
       System.out.println(isPalindrome(s));   
    }
}
true

वैध पलिंड्रोम लेकोडकोड समाधान के लिए जटिलता विश्लेषण

समय जटिलता

पर): n दी गई स्ट्रिंग की लंबाई है। हमें स्ट्रिंग को रैखिक रूप से पुनरावृत्त करना होगा। इसलिए समय जटिलता O (n) होगी।

अंतरिक्ष जटिलता 

पर): फ़िल्टर किए गए स्ट्रिंग और उल्टे स्ट्रिंग को संग्रहीत करने के लिए हमें O (n) अतिरिक्त स्थान की आवश्यकता है।

अनुकूलित दृष्टिकोण (दो बिंदुओं का उपयोग करके)

उपरोक्त दृष्टिकोण में हमने दिए गए स्ट्रिंग को फ़िल्टर किया और इसे स्टोर करने के लिए अतिरिक्त स्थान का उपयोग किया। हम जाँच के लिए दो पॉइंटर्स का उपयोग कर सकते हैं कि क्या यह एक palindrome है या नहीं और हमें अतिरिक्त मेमोरी बनाकर इसे फ़िल्टर करने या सहेजने की आवश्यकता नहीं है।

1. हम क्या कर सकते हैं दो सूचक चर ले, प्रारंभ और समाप्त और उन्हें इनपुट स्ट्रिंग के दो सिरों के साथ इंगित करें।
2. अब आगे बढ़ें प्रारंभ सूचक को दाईं ओर तो यह एक अल्फ़ान्यूमेरिक वर्ण की ओर इंगित करता है। इसी तरह आगे बढ़ें समाप्त पॉइंटर को बायें तो यह एक अल्फ़ान्यूमेरिक वर्ण की ओर भी इशारा करता है।
3. अब जांचें कि दोनों पात्र समान हैं या नहीं (मामलों की अनदेखी):

  • यदि यह समान नहीं है, तो हम जानते हैं कि स्ट्रिंग एक वैध पैलिंड्रोम नहीं है, इसलिए गलत है।
  • आगे अगली पुनरावृत्ति जारी रहती है और अगले अक्षरांकीय वर्ण तक इंगित करने के लिए दोनों बिंदुओं को स्थानांतरित करने की समान प्रक्रिया को दोहराते हैं शुरू.

4. लूप खत्म होने के बाद, स्ट्रिंग को पैलिंड्रोम कहा जाता है, इसलिए यह सच है।

मान्य पलिंड्रोम लेटेकोड समाधान के लिए कार्यान्वयन

C ++ प्रोग्राम

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

bool isAlphaNum(char c)
{
    if( (48<=c && c<=57) || (65<=c && c<=90) || (97<=c && c<=122)) 
        return true;
    return false;
}
    
char lowerCase(char c)
{
    if(65<=c && c<=90)
        return c+32;
    else 
        return c;
}
    
bool isPalindrome(string s) 
{
        int start=0,end=s.size()-1;
        
        while(start<end)
        {
            while(start<end && !isAlphaNum(s[start])) start++;
            while(start<end && !isAlphaNum(s[end])) end--;
           
            if(lowerCase(s[start])!=lowerCase(s[end]))  return false; 
            
            start++;
            end--;
        }
        
        return true;

}

int main() 
{
    string s="A man, a plan, a canal: Panama";
    if(isPalindrome(s))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

  return 0; 
}
true

जावा प्रोग्राम

import java.lang.*;

class Rextester
{  
    static boolean isAlphaNum(char c)
    {
        if( (48<=c && c<=57) || (65<=c && c<=90) || (97<=c && c<=122)) 
            return true;
        else
            return false;
    }
    
    static char lowerCase(char c)
    {
        if(65<=c && c<=90)
            return (char)(c+32);
        else 
            return c;
    }
    
    public static boolean isPalindrome(String s) 
    {
       int start=0,end=s.length()-1;
        
        while(start<end)
        {
            while(start<end && !isAlphaNum(s.charAt(start))) start++;
            while(start<end && !isAlphaNum(s.charAt(end))) end--;
           
            if(lowerCase(s.charAt(start))!=lowerCase(s.charAt(end)))  
                return false; 
            
            start++;
            end--;
        }
        
        return true;
        
    }
    
    public static void main(String args[])
    {
       String s="A man, a plan, a canal: Panama";
       System.out.println(isPalindrome(s));   
    }
}
true

वैध पलिंड्रोम लेकोडकोड समाधान के लिए जटिलता विश्लेषण

समय जटिलता

पर): हम केवल एक बार स्ट्रिंग के प्रत्येक चरित्र का दौरा कर रहे हैं। इसलिए समय जटिलता O (n) है।

अंतरिक्ष जटिलता 

ओ (1): हमें यहां किसी अतिरिक्त मेमोरी की आवश्यकता नहीं है।