වලංගු පාලින්ඩ්‍රෝම් ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇමේසන් Apple ජංගම දුරකථන බ්ලූම්බර්ග් ෆේස්බුක් මයික්රොසොෆ්ට් ඔරකල් වේෆෙයාර්
String පොයින්ටර් දෙකක්

ගැටළු ප්රකාශය

පේළියකි, එය අක්ෂර වින්‍යාසය පමණක්ද යන්න තීරණය කළ යුතුය, අක්ෂර සංඛ්‍යා පමණක් එනම් සංඛ්‍යා සහ අක්ෂර පමණක් සලකා බලමු. අක්ෂර අක්ෂර සඳහා වන අවස්ථා ද අප විසින් නොසලකා හැරිය යුතුය.

උදාහරණයක්

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

පැහැදිලි කිරීම:

“අමානප්ලානාකනල් පැනමා” යනු වලංගු පාලින්ඩ්‍රෝමයකි.

"race a car"
false

පැහැදිලි කිරීම:

“රේස්කාර්” යනු පාලින්ඩ්‍රෝමය නොවේ.

බොළඳ ප්‍රවේශය (ප්‍රතිලෝම සමඟ සංසන්දනය කිරීම)

නූලක් palindrome ද නැද්ද යන්න පරීක්ෂා කිරීම සඳහා අපට එය ආපසු හැරවිය හැකි අතර එය මුල් නූල සමඟ සංසන්දනය කළ හැකිය. ආපසු හැරවීමෙන් පසු එය සමාන වේ නම් දී ඇති නූල් පාලින්ඩ්‍රෝමය වේ.
මෙම ගැටලුවේදී හෝඩිය සහ සංඛ්‍යා හැර අනෙක් සියලුම අක්ෂර නොසලකා හැරිය යුතුය. ඒ සඳහා අපට ලබා දී ඇති නූල පෙරණය කර පෙරහන් කළ නූල නව විචල්‍යයකින් සුරැකිය හැක. උදාහරණයක් ගනිමු:

වලංගු පාලින්ඩ්‍රෝම් ලීට්කෝඩ් විසඳුම

 

 

 

 

අපට පෙරහන් කළ නූලක් දැකිය හැකි අතර ආපසු හරවන ලද පෙරහන් නූල් සමාන නොවේ, එබැවින් එය වලංගු පාලින්ඩ්‍රෝම් නොවේ.

වලංගු පාලින්ඩ්‍රෝම් ලීට්කෝඩ් විසඳුම සඳහා ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

#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): අපට මෙහි අමතර මතකයක් අවශ්‍ය නොවේ.