वैध पालिंड्रोम लीटकोड सोल्यूशन  


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन सफरचंद ब्लूमबर्ग फेसबुक मायक्रोसॉफ्ट ओरॅकल वेईफेअर
अल्गोरिदम कोडिंग मुलाखत मुलाखतीची तयारी लेटकोड LeetCodeSolutions अक्षरमाळा दोन पॉईंटर्स

समस्या विधान  

दिले एक स्ट्रिंग, आम्ही केवळ अल्फान्युमेरिक वर्ण म्हणजेच संख्या आणि वर्णमाला विचारात घेऊन पॅलिंड्रोम असल्याचे निर्धारित केले पाहिजे. आम्हाला वर्णमालाच्या वर्णांकडे देखील दुर्लक्ष करावे लागेल.

उदाहरण

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

स्पष्टीकरण:

“अमानाप्लानाकनालपानामा” एक वैध पालिंड्रोम आहे.

"race a car"
false

स्पष्टीकरण:

“रेसॅकार” हा पालिंड्रोम नाही.

भोळे दृष्टिकोन (उलट तुलना)  

एखादी स्ट्रिंग पॅलिंड्रोम आहे की नाही हे तपासण्यासाठी आम्ही त्यास फक्त उलट करू शकतो आणि मूळ स्ट्रिंगशी तुलना करू शकतो. उलट राहिल्यानंतर समान राहिल्यास दिलेली स्ट्रिंग पालिंड्रोम आहे.
या समस्येमध्ये आम्हाला अक्षरे आणि संख्या वगळता सर्व पात्रांकडे दुर्लक्ष करावे लागेल. त्यासाठी आम्ही दिलेली स्ट्रिंग फिल्टर करू शकतो आणि सर्व अवांछित अक्षरे काढून नवीन व्हेरिएबलमध्ये फिल्टर केलेली स्ट्रिंग सेव्ह करू शकतो. एक उदाहरण घेऊ.

वैध पालिंड्रोम लीटकोड सोल्यूशन

 

 

 

 

आम्ही फिल्टरिंग स्ट्रिंग पाहू शकतो आणि उलट फिल्टर केलेली स्ट्रिंग बरोबर नाही, म्हणून ती वैध पॅलिंड्रोम नाही.

वैध पॅलिंड्रोम लीटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#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 ही दिलेल्या स्ट्रिंगची लांबी आहे. आपल्याला स्ट्रिंग रेषेत पुनरावृत्ती करणे आवश्यक आहे. म्हणून वेळ जटिलता ओ (एन) असेल.

हे सुद्धा पहा
बायनरी ट्रीचे कर्ण ट्रॅव्हर्सल

स्पेस कॉम्प्लेक्सिटी 

ओ (एन): आम्हाला फिल्टर केलेली स्ट्रिंग आणि उलट स्ट्रिंग संचयित करण्यासाठी ओ (एन) अतिरिक्त जागा आवश्यक आहे.

ऑप्टिमाइझ केलेला दृष्टीकोन (दोन पॉईंटर्स वापरुन)  

वरील पध्दतीने आम्ही दिलेली स्ट्रिंग फिल्टर केली आणि ती संग्रहित करण्यासाठी अतिरिक्त जागा वापरली. आम्ही पॅलिंड्रोम आहे की नाही हे तपासण्यासाठी दोन पॉईंटर्स देखील वापरू शकतो आणि आम्हाला अतिरिक्त मेमरी तयार करुन ते फिल्टर किंवा जतन करण्याची आवश्यकता नाही.

१. आपण जे करू शकतो ते म्हणजे दोन पॉईंटर व्हेरिएबल्स. प्रारंभ आणि शेवट आणि इनपुट स्ट्रिंगच्या दोन टोकांसह त्यांना दर्शवा.
2. आता हलवा प्रारंभ पॉईंटर ते उजवे जेणेकरून ते अल्फान्यूमेरिक वर्णात निर्देश करते. त्याचप्रमाणे हलवा शेवट डावीकडून पॉईंटर जेणेकरून ते अल्फान्यूमेरिक कॅरेक्टरला देखील निर्देशित करते.
Now. आता दोन्ही वर्ण एकसारखे आहेत की नाही ते पहा (प्रकरणांकडे दुर्लक्ष करत नाही):

  • जर ते समान नसेल तर आपल्याला माहित आहे की स्ट्रिंग एक वैध पॅलिंड्रोम नाही, म्हणूनच खोटे परत जा.
  • अन्यथा पुढील पुनरावृत्तीवर जाणे चालू ठेवा आणि दोन्ही पॉइंटर्स हलविण्याची समान प्रक्रिया पुन्हा करा प्रारंभ करा.

Lo. पळवाट संपल्यानंतर, स्ट्रिंग पॅलिंड्रोम असे म्हटले जाते, म्हणूनच ते खरे होते.

वैध पॅलिंड्रोम लीटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#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

वैध पॅलिंड्रोम लीटकोड सोल्यूशनसाठी जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन): आम्ही स्ट्रिंगच्या प्रत्येक पात्राला फक्त एकदाच भेट देत आहोत. म्हणून वेळेची जटिलता ओ (एन) आहे.

हे सुद्धा पहा
बॅलन्स्ड स्ट्रिंग्स लीटकोड सोल्यूशनमध्ये एक स्ट्रिंग विभाजित करा

स्पेस कॉम्प्लेक्सिटी 

ओ (1): आम्हाला येथे कोणत्याही अतिरिक्त मेमरीची आवश्यकता नाही.