Valid Palindrome Leetcode Həlli

Problem bəyanat

Verilmiş a sim, yalnız alfasayısal simvolları, yəni yalnız rəqəmləri və əlifbaları nəzərə alaraq palindrom olub olmadığını müəyyənləşdirməliyik. Əlifba simvolları üçün halları da görməməyimiz lazımdır.

misal

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

true

Explanation:

“AmanaplanacanalPanama” etibarlı bir palindromdur.

"race a car"

false

Explanation:

“Racecar” palindrom deyil.

Sadəlövh yanaşma (tərs ilə müqayisə)

Bir ipin palindrom olub olmadığını yoxlamaq üçün onu tərs edib orijinal simlə müqayisə edə bilərik. Geri qaldıqdan sonra bərabər qalsa, verilən sətir palindromdur.
Bu problemdə əlifbalar və rəqəmlər xaricindəki bütün simvollara məhəl qoymamalıyıq. Bunun üçün verilən sətri süzə bilərik və istənməyən simvolları silməklə süzülmüş sətri yeni bir dəyişkən saxlaya bilərik. Nümunə götürək:

 

 

 

 

Süzülmüş sətri görə bilərik və tərs süzülmüş sətir bərabər deyil, ona görə də etibarlı palindrom deyil.

Valid Palindrome Leetcode Həlli üçün tətbiqetmə

C ++ Proqramı

#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 Proqramı

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

Valid Palindrome Leetcode Solution üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (n): n - verilən sətrin uzunluğu. Sətri xətti olaraq təkrarlamalıyıq. Beləliklə zaman mürəkkəbliyi O (n) olacaqdır.

Kosmik Mürəkkəblik 

O (n): Süzülmüş simli və tərs simli saxlamaq üçün O (n) əlavə boşluğa ehtiyacımız var.

Optimallaşdırılmış yanaşma (iki göstəricidən istifadə etməklə)

Yuxarıdakı yanaşmada verilmiş sətri süzdük və saxlamaq üçün əlavə yer istifadə etdik. Palindrom olub olmadığını yoxlamaq üçün iki göstəricidən istifadə edə bilərik və əlavə yaddaş yaradaraq süzməməyimizə və saxlamağımıza ehtiyac yoxdur.

1. Nə edə biləriksə, iki göstərici dəyişəni götürək, Başlamaq və son və onları giriş sətrinin iki ucu ilə göstərin.
2. İndi hərəkət edin Başlamaq işarəsi sağa, beləcə alfasayısal bir işarəyə işarə edir. Eynilə hərəkət edin son göstərici sola, beləliklə əlifba və ədədi işarəsinə işarə edir.
3. İndi hər iki simvolun eyni olub olmadığını yoxlayın (hallara məhəl qoymadan):

• Əgər bərabər deyilsə, onda sətirin etibarlı palindrom olmadığını bilirik, buna görə false olaraq qayıdırıq.
• Başqası növbəti təkrarlamağa davam edin və hər iki göstəricini növbəti əlifba və rəqəm simvoluna qədər göstərmək üçün hərəkət etdirin başlamaq.

4. Döngə bitdikdən sonra ipin palindrom olduğu deyilir və bu səbəbdən geriyə qayıdır.

Valid Palindrome Leetcode Həlli üçün tətbiqetmə

C ++ Proqramı

#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 Proqramı

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

Valid Palindrome Leetcode Solution üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (n): Sətrin hər bir simvolunu yalnız bir dəfə ziyarət edirik. Beləliklə zamanın mürəkkəbliyi O (n) -dir.

Kosmik Mürəkkəblik 

O (1): Burada əlavə yaddaşa ehtiyacımız yoxdur.