유효한 회문

주어진 현 길이 n의 s. 문자열이 유효한 회문인지 확인하는 프로그램을 작성하십시오. 그렇지 않은 경우 문자열에서 최대 한 문자를 삭제하여 회문으로 만들 수 있습니다.

역방향과 동일한 문자열을 회문이라고합니다.

예 :

1. string = "nitin"및 reverse string = "nitin"은 동일하므로 회문입니다.
2. string = "apple"및 reverse string = "elppa"는 동일하지 않으므로 회문이 아닙니다.

핀

예

입력 : s =“abcdba”

출력: 예 ( 'c'또는 'd'제거)

입력 : s = "abba"

출력: 예 (이미 회문)

입력 : s = "파란색"

출력: 아니

유효한 회문에 대한 알고리즘

이제 우리는 가장 간단한 방법으로 문제 설명을 이해합니다. 이제 구현 부분은 구현에 사용되는 알고리즘으로 이동합니다.

1. 문자열을 초기화합니다.
2. 시작 인덱스와 끝 인덱스 포인터를 사용하여 순회를 시작합니다.
3. 두 인덱스의 문자가 동일한 증가 시작 포인터와 감소 끝 포인터인지 확인하십시오. 시작 인덱스가 끝 인덱스보다 크거나 같으면 true를 반환합니다.
4. 그렇지 않으면 이러한 문자 중 하나를 제거하여 회문을 만드십시오.
5. 시작 인덱스에서 문자를 제거하면 회문이 발생하면 true를 반환합니다.
6. 그렇지 않으면 끝 인덱스에서 문자를 제거하면 회문이 true를 반환합니다.
7. 그렇지 않으면 false를 반환합니다.

유효한 회문을 확인하는 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

유효한 회문을 확인하는 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