גילטיק פּאַלינדראָמע לעעטקאָדע סאַלושאַן


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַמאַזאָן עפּל בלומבערג facebook מייקראָסאָפֿט אָראַקל ווייַפאַיר
שטריקל צוויי פּאָינטערס

פּראָבלעם סטאַטעמענט

געגעבן אַ שטריקלמיר מוזן באַשליסן צי עס איז אַ פּאַלינדראָום, בלויז באַטראַכטן אַלפאַנומעריק אותיות, דאָס הייסט נומערן און אַלפאַבעץ. מיר מוזן אויך איגנאָרירן פאלן פֿאַר אלפאבעט אותיות.

בייַשפּיל

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

דערקלערונג:

"AmanaplanacanalPanama" איז אַ גילטיק פּאַלינדראָמע.

"race a car"
false

דערקלערונג:

"ראַסעאַקאַר" איז ניט אַ פּאַלינדראָום.

נאַיוו צוגאַנג (קאַמפּערינג מיט פאַרקערט)

צו קאָנטראָלירן צי אַ שטריקל איז פּאַלינדראָמע אָדער נישט, מיר קענען סימפּלי פאַרקערט עס און פאַרגלייכן עס מיט דער אָריגינעל שטריקל. נאָך ריווערסינג אויב עס בלייבט גלייַך, די געגעבן שטריקל איז אַ פּאַלינדראָום.
אין דעם פּראָבלעם מיר האָבן צו איגנאָרירן אַלע די אותיות אַחוץ אַלפאַבעץ און נומערן. דעריבער, מיר קענען פילטער די געגעבן שטריקל און שפּאָרן די געפילטערט שטריקל אין אַ נייַע בייַטעוודיק דורך רימוווינג אַלע אַנוואָנטיד אותיות. לאָמיר נעמען אַ בייַשפּיל:

גילטיק פּאַלינדראָמע לעעטקאָדע סאַלושאַן

 

 

 

 

מיר קענען זען פילטערד שטריקל און ריווערסט געפילטערט שטריקל איז נישט גלייַך, דערפאר עס איז נישט אַ גילטיק פּאַלינדראָום.

ימפּלאַמענטיישאַן פֿאַר גילטיק פּאַלינדראָמע לעעטקאָדע סאַלושאַן

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): n איז די לענג פון די געגעבן שטריקל. מיר דאַרפֿן צו יבערקערן די שטריקל לינעאַרלי. דעריבער צייט קאַמפּלעקסיטי וועט זיין אָ (n).

ספעיס קאַמפּלעקסיטי 

אָ (n): מיר דאַרפֿן O (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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר גילטיק פּאַלינדראָמע לעעטקאָדע סאַלושאַן

צייט קאַמפּלעקסיטי

אָ (n): מיר באזוכן יעדער כאַראַקטער פון דער שטריקל נאָר אַמאָל. דעריבער צייט קאַמפּלעקסיטי איז אָ (n).

ספעיס קאַמפּלעקסיטי 

אָ (1): מיר טאָן ניט דאַרפֿן קיין עקסטרע זכּרון.