የሚሰራ ፓልindሮም ሌትኮድ መፍትሄ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ፓም ብሉምበርግ ፌስቡክ የ Microsoft በ Oracle ዌይፌር
ሕብረቁምፊ ሁለት ጠቋሚዎች

የችግሩ መግለጫ

የተሰጠው ሀ ክር፣ የቁጥር ፊደላትን ማለትም ቁጥሮችን እና ፊደሎችን ብቻ ከግምት ውስጥ በማስገባት አንድ ፓልደሮም መሆኑን መወሰን አለብን። እንዲሁም ለፊደል ገጸ-ባህሪያት ጉዳዮችን ችላ ማለት አለብን ፡፡

ለምሳሌ

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

ማብራሪያ:

“AmanaplanacanalPanama” ትክክለኛ ፓሊንድሮም ነው።

"race a car"
false

ማብራሪያ:

“ዘርአካር” ፓሊንድሮም አይደለም።

የተሳሳተ አቀራረብ (ከተገላቢጦሽ ጋር ማወዳደር)

አንድ ገመድ ፓሊንድሮም መሆኑን ወይም አለመሆኑን ለማጣራት በቀላሉ መለወጥ እና ከዋናው ገመድ ጋር ማወዳደር እንችላለን። በእኩልነት ከቀጠለ ከተቀየረ በኋላ የተሰጠው ገመድ ፓሊንድሮም ነው ፡፡
በዚህ ችግር ውስጥ ከፊደሎች እና ቁጥሮች በስተቀር ሁሉንም ቁምፊዎች ችላ ማለት አለብን ፡፡ ስለዚህ ለዚያ የተሰጠውን ገመድ አጣርተን ሁሉንም የማይፈለጉ ቁምፊዎችን በማስወገድ የተጣራውን ገመድ በአዲስ ተለዋዋጭ ውስጥ ማስቀመጥ እንችላለን ፡፡ አንድ ምሳሌ እንውሰድ

የሚሰራ ፓልindሮም ሌትኮድ መፍትሄ

 

 

 

 

የተጣራ ህብረቁምፊ ማየት እንችላለን እና የተገላቢጦሽ የተጣራ ገመድ እኩል አይደለም ፣ ስለሆነም ትክክለኛ ፓልደሮም አይደለም ፡፡

ለትግበራ ፓሊንድሮም ሌትኮድ መፍትሄ ተግባራዊነት

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

ውስብስብነት ያለው ትንታኔ ለትክክለኛው ፓሊንድሮም ሌትኮድ መፍትሄ

የጊዜ ውስብስብነት

ኦ (n): n የተሰጠው ገመድ ርዝመት ነው። ሕብረቁምፊውን በመስመር ላይ ማመጣጠን አለብን ፡፡ ስለዚህ የጊዜ ውስብስብነት O (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

የጃቫ ፕሮግራም

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): እያንዳንዱን የሕብረቁምፊ ቁምፊ የምንጎበኘው አንድ ጊዜ ብቻ ነው ፡፡ ስለዚህ የጊዜ ውስብስብነት O (n) ነው።

የቦታ ውስብስብነት 

ኦ (1) እዚህ ምንም ተጨማሪ ማህደረ ትውስታ አያስፈልገንም።