ਵੈਧ ਪਲਿੰਡਰੋਮ ਲੀਟਕੋਡ ਹੱਲ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਸੇਬ ਬਲੂਮਬਰਗ ਫੇਸਬੁੱਕ Microsoft ਦੇ ਓਰੇਕਲ ਵੇਫੈਅਰ
ਸਤਰ ਦੋ ਪੁਆਇੰਟਰ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਦਿੱਤਾ ਗਿਆ ਏ ਸਤਰ, ਸਾਨੂੰ ਇਹ ਨਿਰਧਾਰਤ ਕਰਨਾ ਪਏਗਾ ਕਿ ਕੀ ਇਹ ਇਕ ਪਾਲੀਂਡਰੋਮ ਹੈ, ਸਿਰਫ ਵਰਣਮਾਲਾ ਦੇ ਅੱਖਰ, ਜਿਵੇਂ ਕਿ ਸਿਰਫ ਸੰਖਿਆਵਾਂ ਅਤੇ ਵਰਣਮਾਲਾ. ਸਾਨੂੰ ਵਰਣਮਾਲਾ ਦੇ ਕਿਰਦਾਰਾਂ ਲਈ ਵੀ ਨਜ਼ਰ ਅੰਦਾਜ਼ ਕਰਨਾ ਪਏਗਾ.

ਉਦਾਹਰਨ

"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 ਦਿੱਤੀ ਗਈ ਸਤਰ ਦੀ ਲੰਬਾਈ ਹੈ. ਸਾਨੂੰ ਸਤਰ ਨੂੰ ਰੇਖਿਕ ਰੂਪ ਵਿੱਚ ਦੁਹਰਾਉਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਇਸ ਲਈ ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ O (n) ਹੋਵੇਗੀ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ 

ਓ (ਐਨ): ਫਿਲਟਰ ਕੀਤੀਆਂ ਤਾਰਾਂ ਅਤੇ ਉਲਟ ਸਤਰਾਂ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ ਸਾਨੂੰ O (n) ਵਾਧੂ ਥਾਂ ਚਾਹੀਦੀ ਹੈ.

ਅਨੁਕੂਲ ਪਹੁੰਚ (ਦੋ ਪੁਆਇੰਟਰ ਦੀ ਵਰਤੋਂ ਕਰਦਿਆਂ)

ਉਪਰੋਕਤ ਪਹੁੰਚ ਵਿਚ ਅਸੀਂ ਦਿੱਤੀ ਗਈ ਸਤਰ ਫਿਲਟਰ ਕੀਤੀ ਅਤੇ ਇਸ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ ਵਧੇਰੇ ਥਾਂ ਦੀ ਵਰਤੋਂ ਕੀਤੀ. ਅਸੀਂ ਇਹ ਜਾਂਚ ਕਰਨ ਲਈ ਦੋ ਪੁਆਇੰਟਰਾਂ ਦੀ ਵਰਤੋਂ ਵੀ ਕਰ ਸਕਦੇ ਹਾਂ ਕਿ ਕੀ ਇਹ ਇਕ ਪਾਲੀਂਡਰੋਮ ਹੈ ਜਾਂ ਨਹੀਂ ਅਤੇ ਸਾਨੂੰ ਵਾਧੂ ਮੈਮੋਰੀ ਬਣਾ ਕੇ ਫਿਲਟਰ ਕਰਨ ਜਾਂ ਬਚਾਉਣ ਦੀ ਜ਼ਰੂਰਤ ਨਹੀਂ ਹੈ.

1. ਅਸੀਂ ਜੋ ਕਰ ਸਕਦੇ ਹਾਂ ਉਹ ਹੈ ਦੋ ਪੁਆਇੰਟਰ ਵੇਰੀਏਬਲ, ਸ਼ੁਰੂ ਅਤੇ ਅੰਤ ਅਤੇ ਇਨਪੁਟ ਸਟਰਿੰਗ ਦੇ ਦੋ ਸਿਰੇ ਦੇ ਨਾਲ ਇਸ਼ਾਰਾ ਕਰੋ.
2. ਹੁਣ ਮੂਵ ਕਰੋ ਸ਼ੁਰੂ ਪੁਆਇੰਟਰ ਤੋਂ ਸੱਜੇ ਤਾਂ ਇਹ ਇਕ ਅੱਖਰ ਅੱਖਰ ਵੱਲ ਇਸ਼ਾਰਾ ਕਰਦਾ ਹੈ. ਇਸੇ ਤਰਾਂ ਚੱਲੋ ਅੰਤ ਖੱਬੇ ਵੱਲ ਸੰਕੇਤ ਕਰਦਾ ਹੈ ਤਾਂ ਇਹ ਅੱਖ਼ਰ ਦੇ ਅੱਖਰ ਨੂੰ ਵੀ ਦਰਸਾਉਂਦਾ ਹੈ.
3. ਹੁਣ ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਦੋਵੇਂ ਪਾਤਰ ਇਕੋ ਜਿਹੇ ਹਨ ਜਾਂ ਨਹੀਂ (ਅਣਡਿੱਠ ਕੇਸ):

  • ਜੇ ਇਹ ਬਰਾਬਰ ਨਹੀਂ ਹੈ ਤਾਂ ਅਸੀਂ ਜਾਣਦੇ ਹਾਂ ਕਿ ਸਤਰ ਇੱਕ ਵੈਧ ਪਾਲੀਂਡਰੋਮ ਨਹੀਂ ਹੈ, ਇਸ ਲਈ ਗਲਤ ਵਾਪਸ ਆਓ.
  • ਹੋਰ ਅਗਲੀ ਪੁਨਰਗਠਨ ਤੇ ਜਾਰੀ ਰੱਖੋ ਅਤੇ ਦੋਵਾਂ ਪੁਆਇੰਟਰਾਂ ਨੂੰ ਅਗਲੇ ਅਲਫ਼ਾਨਮੂਮਿਕ ਅੱਖਰ ਵੱਲ ਇਸ਼ਾਰਾ ਕਰਨ ਲਈ ਉਸੇ ਪ੍ਰਕਿਰਿਆ ਨੂੰ ਦੁਹਰਾਓ ਸ਼ੁਰੂ ਕਰੋ.

4. ਲੂਪ ਖ਼ਤਮ ਹੋਣ ਤੋਂ ਬਾਅਦ, ਤਾਰ ਨੂੰ ਪਾਲੀਂਡਰੋਮ ਕਿਹਾ ਜਾਂਦਾ ਹੈ, ਇਸ ਲਈ ਸਹੀ ਵਾਪਿਸ ਆਓ.

ਵੈਲਡ ਪਲਿੰਡਰੋਮ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਲਈ ਲਾਗੂਕਰਣ

ਸੀ ++ ਪ੍ਰੋਗਰਾਮ

#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): ਸਾਨੂੰ ਇੱਥੇ ਕਿਸੇ ਵਾਧੂ ਮੈਮੋਰੀ ਦੀ ਲੋੜ ਨਹੀਂ ਹੈ.