მოქმედებს Palindrome Leetcode Solution


Რთული ტური Easy
ხშირად ეკითხებიან Amazon Apple Bloomberg Facebook microsoft Oracle Wayfair
სიმებიანი ორი მაჩვენებელი

პრობლემის განცხადება

მოცემულია ა სიმებიანი, ჩვენ უნდა დავადგინოთ არის თუ არა იგი პალინდრომი, მხოლოდ ალფანუმერული სიმბოლოების გათვალისწინებით, ანუ მხოლოდ ციფრებისა და ანბანის მიხედვით. ჩვენ ასევე უგულებელვყოფთ ანბანის სიმბოლოების შემთხვევებს.

მაგალითი

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

განმარტება:

"AmanaplanacanalPanama" მოქმედი პალინდრომია.

"race a car"
false

განმარტება:

"რასაკარი" არ არის პალინდრომი.

გულუბრყვილო მიდგომა (რევერსის შედარება)

იმის შესამოწმებლად, არის თუ არა სტრიქონი პალინდრომი, შეგვიძლია უბრალოდ გადავაბრუნოთ იგი და შევადაროთ ორიგინალ სტრიქონს. უკუქცევის შემდეგ, თუ იგი ტოლია, მაშინ მოცემული სტრიქონი არის პალინდრომი.
ამ პრობლემის დროს ჩვენ უგულებელყოფთ ყველა სიმბოლოს, გარდა დამწერლობისა და ციფრებისა. ასე რომ, ჩვენ შეგვიძლია გავფილტროთ მოცემული სტრიქონი და შევინახოთ გაფილტრული სტრიქონი ახალ ცვლადში, ყველა არასასურველი სიმბოლოს ამოღებით. ავიღოთ მაგალითი:

მოქმედებს Palindrome Leetcode Solution

 

 

 

 

ჩვენ შეგვიძლია დავინახოთ გაფილტრული სტრიქონი და უკუგანვითარებული გაფილტრული სტრიქონი არ არის ტოლი, შესაბამისად, ის არ არის მოქმედი პალინდრომი.

განხორციელება Valid Palindrome Leetcode Solution- ისთვის

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

ჯავა პროგრამა

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- ისთვის

დროის სირთულე

O (n): n მოცემული სტრიქონის სიგრძეა. ჩვენ გვჭირდება სტრიქონის ხაზოვანი განმეორება. ამრიგად, დროის სირთულე იქნება O (n).

სივრცის სირთულე 

O (n): ჩვენ გვჭირდება O (n) დამატებითი სივრცე გაფილტრული სტრიქონის და საპირისპირო სტრიქონის შესანახად.

ოპტიმიზირებული მიდგომა (ორი მაჩვენებლის გამოყენებით)

ზემოთ მოცემულ მიდგომაში ჩვენ გავაფილტრეთ მოცემული სტრიქონი და გამოვიყენეთ დამატებითი ადგილი მის შესანახად. ჩვენ ასევე შეგვიძლია გამოვიყენოთ ორი მანიშნებელი იმის შესამოწმებლად, არის თუ არა იგი პალინდრომი და არ უნდა გავაფილტროთ ან დავიმახსოვროთ დამატებითი მეხსიერების შექმნით.

1. რისი გაკეთება შეგვიძლია არის ორი მაჩვენებლის ცვლადი, დაწყება და ბოლო და მიუთითეთ ისინი შემავალი სტრიქონის ორი ბოლოთი.
2. ახლა გადაადგილება დაწყება მაჩვენებელი მარჯვნივ, ამიტომ მიუთითებს ალფანუმერულ სიმბოლოზე. ანალოგიურად გადაადგილება ბოლო მაჩვენებელი მარცხნივ, ამიტომ ის ასევე მიუთითებს ალფანუმერულ სიმბოლოზე.
3. ახლა გადაამოწმეთ, ორივე სიმბოლო იგივეა თუ არა (შემთხვევების უგულებელყოფა):

  • თუ ეს არ არის ტოლი, მაშინ ვიცით, რომ სტრიქონი არ არის მოქმედი პალინდრომი, ამიტომ დაბრუნდება false.
  • შემდეგ გააგრძელეთ შემდეგი განმეორება და გაიმეორეთ იგივე მაჩვენებლის გადაადგილების პროცესი ორივე ალფანუმერული სიმბოლოზე გადასასვლელად დაწყება.

4. მარყუჟის დასრულების შემდეგ, სიმებიანი ამბობენ, რომ არის პალინდრომი, ამიტომ დაბრუნდება true.

განხორციელება Valid Palindrome Leetcode Solution- ისთვის

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

ჯავა პროგრამა

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- ისთვის

დროის სირთულე

O (n): ჩვენ მხოლოდ ერთხელ ვსტუმრობთ სტრიქონის თითოეულ პერსონაჟს. ამრიგად, დროის სირთულე არის O (n).

სივრცის სირთულე 

O (1): აქ დამატებითი მეხსიერება არ გვჭირდება.