ಮಾನ್ಯ ಪಾಲಿಂಡ್ರೋಮ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಆಪಲ್ ಬ್ಲೂಮ್ಬರ್ಗ್ ಫೇಸ್ಬುಕ್ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಒರಾಕಲ್ ವೇಫೇರ್
ಸ್ಟ್ರಿಂಗ್ ಎರಡು ಪಾಯಿಂಟರ್‌ಗಳು

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

ನೀಡಲಾಗಿದೆ ಸ್ಟ್ರಿಂಗ್, ಇದು ಪಾಲಿಂಡ್ರೋಮ್ ಎಂದು ನಾವು ನಿರ್ಧರಿಸಬೇಕು, ಕೇವಲ ಆಲ್ಫಾನ್ಯೂಮರಿಕ್ ಅಕ್ಷರಗಳನ್ನು ಅಂದರೆ ಸಂಖ್ಯೆಗಳು ಮತ್ತು ವರ್ಣಮಾಲೆಗಳನ್ನು ಮಾತ್ರ ಪರಿಗಣಿಸುತ್ತೇವೆ. ವರ್ಣಮಾಲೆಯ ಅಕ್ಷರಗಳಿಗಾಗಿ ನಾವು ಪ್ರಕರಣಗಳನ್ನು ನಿರ್ಲಕ್ಷಿಸಬೇಕಾಗಿದೆ.

ಉದಾಹರಣೆ

"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) ಆಗಿರುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ 

ಒ (ಎನ್): ಫಿಲ್ಟರ್ ಮಾಡಿದ ಸ್ಟ್ರಿಂಗ್ ಮತ್ತು ರಿವರ್ಸ್ಡ್ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಸಂಗ್ರಹಿಸಲು ನಮಗೆ ಒ (ಎನ್) ಹೆಚ್ಚುವರಿ ಸ್ಥಳ ಬೇಕು.

ಆಪ್ಟಿಮೈಸ್ಡ್ ಅಪ್ರೋಚ್ (ಎರಡು ಪಾಯಿಂಟರ್‌ಗಳನ್ನು ಬಳಸುವುದು)

ಮೇಲಿನ ವಿಧಾನದಲ್ಲಿ ನಾವು ಕೊಟ್ಟಿರುವ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಫಿಲ್ಟರ್ ಮಾಡಿದ್ದೇವೆ ಮತ್ತು ಅದನ್ನು ಸಂಗ್ರಹಿಸಲು ಹೆಚ್ಚುವರಿ ಸ್ಥಳವನ್ನು ಬಳಸಿದ್ದೇವೆ. ಇದು ಪಾಲಿಂಡ್ರೋಮ್ ಅಥವಾ ಇಲ್ಲವೇ ಎಂದು ಪರಿಶೀಲಿಸಲು ನಾವು ಎರಡು ಪಾಯಿಂಟರ್‌ಗಳನ್ನು ಸಹ ಬಳಸಬಹುದು ಮತ್ತು ಹೆಚ್ಚುವರಿ ಮೆಮೊರಿಯನ್ನು ರಚಿಸುವ ಮೂಲಕ ನಾವು ಅದನ್ನು ಫಿಲ್ಟರ್ ಮಾಡಬೇಕಾಗಿಲ್ಲ ಅಥವಾ ಉಳಿಸಬೇಕಾಗಿಲ್ಲ.

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): ನಮಗೆ ಇಲ್ಲಿ ಯಾವುದೇ ಹೆಚ್ಚುವರಿ ಮೆಮೊರಿ ಅಗತ್ಯವಿಲ್ಲ.