Ισχύει Palindrome  


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Infosys MAQ Nokia o9 λύσεις
κορδόνι Δύο δείκτες

Δεδομένου α κορδόνι s μήκους n. Γράψτε ένα πρόγραμμα για να βρείτε αν η συμβολοσειρά είναι έγκυρη ή όχι. Εάν όχι, μπορείτε να διαγράψετε το πολύ έναν χαρακτήρα από τη συμβολοσειρά για να το κάνετε ένα palindrome.

Κάθε συμβολοσειρά που είναι ίδια με την αντίστροφη, είναι γνωστή ως palindrome.

Για παράδειγμα:

  1. string = "nitin" και reverse string = "nitin" που είναι τα ίδια, επομένως είναι ένα palindrome.
  2. string = "apple" και αντίστροφη συμβολοσειρά = "elppa" που δεν είναι οι ίδιες επομένως δεν είναι palindrome.

Ισχύει PalindromeΚαρφώστε

Παράδειγμα  

Είσοδος: s = "abcdba"

Παραγωγή: Ναι (αφαιρώντας είτε «c» είτε «d»)

Είσοδος: s = "abba"

Παραγωγή: Ναι (ήδη παλινδρομή)

Είσοδος: s = "μπλε"

Παραγωγή: Οχι

Αλγόριθμος για έγκυρο Palindrome  

Τώρα κατανοούμε τη δήλωση προβλήματος με τον απλούστερο τρόπο. Έτσι, τώρα για το μέρος εφαρμογής μεταβείτε στον αλγόριθμο που χρησιμοποιείται για την εφαρμογή.

  1. Αρχικοποιήστε μια συμβολοσειρά.
  2. Ξεκινήστε να διασχίζετε χρησιμοποιώντας το δείκτη έναρξης και το δείκτη τελικού δείκτη.
  3. Ελέγξτε εάν ο χαρακτήρας και στα δύο ευρετήρια είναι ίσος δείκτης έναρξης αύξησης και δείκτης λήξης μείωσης. Εάν το αρχικό ευρετήριο είναι μεγαλύτερο ή ίσο με το τελικό ευρετήριο, επιστρέψτε το true.
  4. Διαφορετικά, δοκιμάστε να δημιουργήσετε palindrome καταργώντας έναν από αυτούς τους χαρακτήρες.
  5. Εάν η κατάργηση του χαρακτήρα κατά την εκκίνηση του ευρετηρίου οδηγεί στην επιστροφή του palindrome.
  6. Διαφορετικά, εάν η κατάργηση του χαρακτήρα στο τέλος του ευρετηρίου έχει ως αποτέλεσμα την επιστροφή αληθινού palindrome.
  7. Αλλιώς επιστρέφει ψευδής.

Πρόγραμμα C ++ για έλεγχο Valid Palindrome  

#include <bits/stdc++.h> 
using namespace std; 

bool isPalindrome(string::iterator low, string::iterator high){ 
    while(low < high){ 
       if(*low != *high) 
          return false; 
       low++; 
       high--; 
    } 
    return true; 
} 
  
bool Palindrome(string s){ 
    int low = 0, high = s.length() - 1; 
  
    while(low < high){ 
        if(s[low] == s[high]){ 
            low++; 
            high--; 
        } 
        else{ 
            if(isPalindrome(s.begin() + low + 1, s.begin() + high)) 
                return true; 
  
            if (isPalindrome(s.begin() + low, s.begin() + high - 1)) 
                return true; 
  
            return false; 
        } 
    } 
  
    return true; 
} 
  
int main(){ 
    string s = "abcdba"; 
    
    if(Palindrome(s)){
        cout<<"Yes";
    } 
    else{
        cout<<"No";
    }
    return 0; 
}
Yes

Πρόγραμμα Java για έλεγχο Valid Palindrome  

import java.util.*; 
  
class validPalindrome{ 
  
    static boolean isPalindrome(String s, int low, int high){ 
        while(low < high){ 
            if(s.charAt(low) != s.charAt(high)) 
                return false; 
            low++; 
            high--; 
        } 
        return true; 
    } 
  
    static boolean Palindrome(String s){ 
  
        int low = 0, high = s.length() - 1; 
  
        while(low < high){ 
  
            if(s.charAt(low) == s.charAt(high)){ 
                low++; 
                high--; 
            }  
            else{ 
  
                if(isPalindrome(s, low + 1, high)) 
                    return true; 
  
                if(isPalindrome(s, low, high - 1)) 
                    return true; 
                return false; 
            } 
        } 
  
        return true; 
    } 
  
    public static void main(String[] args){ 
        String s = "abcdba"; 
        
        if(Palindrome(s)){
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
    } 
} 
Yes

Ανάλυση πολυπλοκότητας  

Χρόνος πολυπλοκότητας

O (n)  όπου n είναι το μήκος της δεδομένης συμβολοσειράς.

Βλέπε επίσης
Διαγράψτε έναν κόμβο από τη συνδεδεμένη λίστα χωρίς επικεφαλής δείκτη

Βοηθητικός χώρος

Ο (1) γιατί δεν χρησιμοποιούμε επιπλέον χώρο εδώ.

Αναφορές