최단 회문

난이도 하드
자주 묻는 질문 아마존 배달 팩트 셋
조회수 47

가장 짧은 회문 문제에서 우리는 길이 l의 s. 그렇지 않은 경우 회문으로 만들기 위해 그 앞에 문자를 추가하십시오. 주어진 문자열을 회문으로 만드는 데 사용되는 최소 문자 수를 인쇄합니다.

최단 회문

입력 : s = ABC

출력: 2 (앞에 c와 b를 추가하면 회문 cbabc가됩니다)

입력 : s = 아바

출력: 1 (앞면을 추가하면 회문 aabbaa가 됨)

간단한 방법

암호알고리즘

  1. 길이가 L 인 문자열 s를 초기화합니다.
  2. 개수와 플래그 변수를 저장할 정수 변수를 만듭니다. 두 변수를 모두 0으로 초기화합니다.
  3. 길이가 0보다 큰 동안 문자열을 탐색합니다. 문자열을 탐색하고 문자열 중간에 도달 할 때까지 시작 문자를 끝 문자와 비교하기 시작합니다. 현재 문자열이 회 문인 경우, 즉 시작 문자가 끝 문자와 같으면 플래그 변수를 1로 업데이트하고 루프를 중단합니다.
  4. 그렇지 않으면 count 변수를 1 씩 증가시키고 문자열의 마지막 문자를 제거합니다.
  5. 플래그 변수가 1이면 카운트를 인쇄합니다.

최단 회문을 찾는 C ++ 프로그램

#include<bits/stdc++.h> 
using namespace std; 
  
bool isPalindrome(string s){ 
    int l = s.length(); 
    int j; 
      
    for(int i=0, j=l-1; i<=j; i++, j--){ 
        if(s[i] != s[j]) 
            return false; 
    } 
    return true; 
} 
  
int main(){ 
    string s = "abc"; 
    int count = 0, f = 0; 
      
    while(s.length()>0){ 
        if(isPalindrome(s)){ 
            f = 1; 
             break; 
        } 
        else{ 
            count++; 
            s.erase(s.begin() + s.length() - 1); 
        } 
    } 
      
    if(f) 
        cout<<count; 
}
2

가장 짧은 회문을 찾는 자바 프로그램

class Palindrome{ 
  
    static boolean isPalindrome(String s){ 
        int l = s.length(); 
  
        for(int i=0, j=l-1; i<=j; i++, j--){ 
            if(s.charAt(i) != s.charAt(j)){ 
                return false; 
            } 
        } 
        return true; 
    } 
  
    public static void main(String[] args){ 
        String s = "abc"; 
        int count = 0, f = 0; 
  
        while(s.length() > 0){ 
            if(isPalindrome(s)){ 
                f = 1; 
                break; 
            } 
            else{ 
                count++; 
  
                s = s.substring(0, s.length() - 1); 
            } 
        } 
  
        if(f == 1){ 
            System.out.println(count); 
        } 
    } 
}
2

복잡성 분석

시간 복잡성 : O (L * L) (L은 문자열의 길이)

보조 공간 : O (1) 우리는 일정한 추가 공간을 사용했기 때문에

효율적인 방법

암호알고리즘

  1. 길이가 L 인 문자열 s를 초기화합니다.
  2. 문자열 변수를 만들고 그 안에 원래 문자열의 반대를 저장합니다.
  3. 문자열의 연결을 저장하고 그 사이에 특수 문자가있는 원래 문자열과 반전 된 문자열의 연결을 저장하는 다른 문자열을 작성하십시오.
  4. lps 배열을 초기화합니다.
  5. 문자열을 탐색하고 lps 배열의 값을 업데이트합니다.
  6. lps 배열을 반환합니다.

최단 회문을 찾는 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
vector<int> computeLPSArray(string s){ 
    int l = s.length(); 
    vector<int> lps(l); 
  
    int len = 0; 
    lps[0] = 0; 
  
    int i = 1; 
    while(i<l){ 
        if(s[i] == s[len]){ 
            len++; 
            lps[i] = len; 
            i++; 
        } 
        else{ 
            if(len != 0){ 
                len = lps[len-1]; 
            } 
            else{ 
                lps[i] = 0; 
                i++; 
            } 
        } 
    } 
    return lps; 
} 
  
int minChar(string s){ 
    string rev = s; 
    reverse(rev.begin(), rev.end()); 
  
    string concat = s + "$" + rev; 
  
    vector<int> lps = computeLPSArray(concat); 
  
    return(s.length() - lps.back()); 
} 
  
int main(){ 
    string s = "abc"; 
    cout<<minChar(s); 
    return 0; 
}
2

가장 짧은 회문을 찾는 자바 프로그램

class Palindrome{ 
  
    public static int[] computeLPSArray(String s){ 
        int l = s.length(); 
        int lps[] = new int[l]; 
        int i = 1, len = 0; 
        lps[0] = 0;
          
        while(i < l){ 
            if(s.charAt(i) == s.charAt(len)){ 
                len++; 
                lps[i] = len; 
                i++; 
            } 
            else{ 
                if(len != 0){ 
                    len = lps[len - 1]; 
                } 
                else{ 
                    lps[i] = 0; 
                    i++; 
                } 
            } 
        } 
        return lps; 
    } 
      
    static int minChar(String s){  
        StringBuilder S = new StringBuilder(); 
        S.append(s); 
          
        String rev = S.reverse().toString(); 
        S.reverse().append("$").append(rev); 
          
        int lps[] = computeLPSArray(S.toString()); 
        return s.length() - lps[S.length() - 1]; 
    } 

    public static void main(String[] args){ 
        String s = "abc"; 
        System.out.println(minChar(s)); 
    } 
}
2

복잡성 분석

시간 복잡성 : O (L) (L은 문자열의 길이)

보조 공간 : L 문자에 추가 공간을 사용했기 때문에 O (L).

참조

Translate »