Палиндромның жарамды кодының шешімі


Күрделілік дәрежесі оңай
Жиі кіреді Amazon алма Bloomberg Facebook Microsoft Oracle Wayfair
String Екі нұсқағыш

Проблемалық мәлімдеме

Берілген жол, біз тек әріптік-цифрлық таңбаларды, яғни тек сандар мен алфавиттерді ескере отырып, оның палиндром екенін анықтауымыз керек. Сондай-ақ, алфавит таңбаларына арналған жағдайларды елемеуіміз керек.

мысал

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

Түсіндіру:

«AmanaplanacanalPanama» - жарамды палиндром.

"race a car"
false

Түсіндіру:

“Racacar” палиндром емес.

Аңғал көзқарас (керісінше)

Жолдың палиндромды немесе жоқ екенін тексеру үшін оны кері айналдырып, оны бастапқы жолмен салыстыра аламыз. Реверстен кейін, егер ол тең болып қалса, онда берілген жол палиндром болады.
Бұл мәселеде біз алфавиттер мен сандардан басқа барлық таңбаларды ескермеуіміз керек. Ол үшін біз берілген жолды сүзіп, барлық қажет емес таңбаларды өшіру арқылы сүзілген жолды жаңа айнымалыға сақтай аламыз. Мысал келтірейік:

Палиндромның жарамды кодының шешімі

 

 

 

 

Біз фильтрленген жолды көре аламыз және кері фильтрленген жол тең емес, сондықтан ол палиндром емес.

Палиндромның жарамды кодтық шешіміне енгізу

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

Java бағдарламасы

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

Палиндромның жарамды кодының ерітіндісіне арналған күрделілікті талдау

Уақыттың күрделілігі

O (n): n - берілген жолдың ұзындығы. Біз жолды сызықтық түрде қайталауымыз керек. Демек, уақыттың күрделілігі O (n) болады.

Ғарыштың күрделілігі 

O (n): Сүзілген жолды және кері жолды сақтау үшін бізге O (n) қосымша орын қажет.

Оңтайландырылған тәсіл (екі нұсқағышты пайдалану)

Жоғарыда біз берілген жолды сүзіп, оны сақтау үшін қосымша орынды пайдаландық. Сондай-ақ, біз палиндромды немесе жоқ екенін тексеру үшін екі көрсеткішті пайдалана аламыз, сондықтан оны қосымша жад құру арқылы сүзіп немесе сақтаудың қажеті жоқ.

1. Біз не істей аламыз, екі көрсеткіштік айнымалыны аламыз, бастау және соңы және оларды кіріс жолының екі ұшымен бағыттаңыз.
2. Енді жылжытыңыз бастау әріптік-цифрлық таңбаны көрсететін етіп оңға қарай бағыттаңыз. Сол сияқты қозғалу соңы солға көрсеткі, сол кезде ол әріптік-сандық белгіні де көрсетеді.
3. Енді екі таңбаның бірдей немесе сәйкес еместігін тексеріңіз (жағдайларды ескермей):

  • Егер ол тең болмаса, онда біз жолдың палиндром емес екенін білеміз, сондықтан false мәнін қайтарамыз.
  • Басқасы келесі қайталануды жалғастырады және екі көрсеткішті келесі әріптік-сандық таңбаға дейін жылжытудың бірдей процесін қайталайды бастау.

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

Java бағдарламасы

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): Біз жолдың әр таңбасына бір рет қана барамыз. Демек уақыттың күрделілігі O (n).

Ғарыштың күрделілігі 

O (1): Бұл жерде бізге қосымша жадтың қажеті жоқ.