Хүчинтэй Палиндром


Хэцүү байдлын түвшин Easy
Байнга асуудаг Infosys MAQ Nokia o9 шийдэл
String Хоёр заагч

Өгсөн мөр s урт n. Тэмдэгт мөр нь палиндромын хүчин төгөлдөр эсэхийг олох програм бич. Хэрэв үгүй ​​бол та палиндром болгохын тулд мөрнөөс хамгийн ихдээ нэг тэмдэгт устгаж болно.

Урвуутай ижил мөрийг палиндром гэдэг.

Жишээлбэл:

  1. мөр = “нитин” ба урвуу мөр = “нитин” ижил тул палиндром юм.
  2. string = "apple" ба reverse string = "elppa" нь ижил биш тул палиндром биш юм.

Хүчинтэй Палиндром

Жишээ нь

Оролт: s = “abcdba”

Үр дүн: Тийм ээ ('c' эсвэл 'd' -ийг хасвал)

Оролт: s = “abba”

Үр дүн: Тиймээ (аль хэдийн палиндром)

Оролт: s = "цэнхэр"

Үр дүн: Үгүй

Хүчин төгөлдөр Палиндромын алгоритм

Одоо бид асуудлын мэдэгдлийг хамгийн энгийнээр ойлгож байна. Тиймээс одоо хэрэгжүүлэх хэсэг нь хэрэгжүүлэхэд ашигладаг алгоритм руу шилжих болно.

  1. Мөр эхлүүлэх.
  2. Эхлэх индекс ба төгсгөлийн индекс заагчийг ашиглан аялж эхэл.
  3. Хоёр индекс дээрх тэмдэгт нь өсөх эхлэлийн заагч ба буурах төгсгөл заагчтай тэнцүү эсэхийг шалгана уу. Хэрэв эхлэх индекс нь төгсгөлийн индексээс их эсвэл тэнцүү байвал буцаана.
  4. Бусад нь эдгээр тэмдэгтүүдийн аль нэгийг арилгаж палиндром хийхийг оролдоорой.
  5. Хэрэв индекс эхлэх үед тэмдэгтийг хасвал палиндром буцааж үнэн болно.
  6. Индексийн төгсгөлд тэмдэгтийг хасвал палиндром үнэн болно.
  7. Бусад нь хуурамчаар буцдаг.

Valid Palindrome-ийг шалгах C ++ програм

#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

Valid Palindrome-ийг шалгах Java програм

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 нь өгөгдсөн мөрний урт юм.

Туслах орон зай

O (1) Учир нь бид энд нэмэлт зай ашигладаггүй.

Refrences