Валидно решение за Leetcode во Палиндром


Ниво на тешкотија Лесно
Често прашувано во Амазон Јаболко Блумберг Facebook Мајкрософт Oracle Wayfair
Стринг Два покажувачи

Изјава за проблем

Со оглед на низа, мора да утврдиме дали станува збор за палиндром, имајќи ги предвид само алфанумеричките знаци, т.е. само броевите и азбуките. Исто така, мора да ги игнорираме случаите за азбучни карактери.

пример

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

објаснување:

„АманапланакананалПанама“ е валиден палиндром.

"race a car"
false

објаснување:

„Тркачот“ не е палиндром.

Наивен пристап (споредување со обратен)

За да провериме дали низата е палиндром или не, можеме едноставно да ја свртиме назад и да ја споредиме со оригиналната низа. По пресврт, ако остане еднаква, дадената низа е палиндром.
Во овој проблем мора да ги игнорираме сите знаци, освен азбуките и броевите. Значи, за тоа можеме да ја филтрираме дадената низа и да ја зачуваме филтрираната низа во нова променлива со отстранување на сите несакани знаци. Ајде да земеме пример:

Валидно решение за Leetcode во Палиндром

 

 

 

 

Можеме да видиме филтрирана низа и обратна филтрирана низа не е еднаква, па затоа не е валиден палиндром.

Имплементација за валидно решение за латен код на палиндром

Програма 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

Анализа на комплексноста за валидно решение за панкром во лек код

Временска комплексност

На): n е должината на дадената низа. Ние треба да ја повторуваме низата линеарно. Оттука, комплексноста на времето ќе биде O (n).

Комплексноста на просторот 

На): Потребен ни е О (n) дополнителен простор за складирање на филтрираната низа и обратната низа.

Оптимизиран пристап (користејќи два покажувачи)

Во горенаведениот пристап, ние ја филтриравме дадената низа и искористивме дополнителен простор за да ја зачуваме. Можеме да користиме и два покажувачи за да провериме дали е палиндром или не и не треба да го филтрираме или зачуваме создавајќи дополнителна меморија.

1. Она што можеме да го направиме е да земеме две варијабли на покажувачот, Почеток крајот и насочете ги со двата краја на влезната низа.
2. Сега преместете ја Почеток покажувач надесно, па покажува на алфанумерички карактер. Слично се движи крајот покажувач налево, така што покажува и на алфанумерички карактер.
3. Сега проверете дали и двата знака се исти или не (игнорирајте случаи):

  • Ако не е еднаква, тогаш знаеме дека стрингот не е валиден палиндром, па оттука вратете неточно.
  • Друго, продолжете на следното повторување и повторете го истиот процес на поместување на обете покажувачи за да покажете на следниот алфанумерички карактер до започнете.

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).

Комплексноста на просторот 

О (1): Овде не ни треба дополнителна меморија.