가장 짧은 회문 문제에서 우리는 현 길이 l의 s. 그렇지 않은 경우 회문으로 만들기 위해 그 앞에 문자를 추가하십시오. 주어진 문자열을 회문으로 만드는 데 사용되는 최소 문자 수를 인쇄합니다.
차례
예
입력 : s = ABC
출력: 2 (앞에 c와 b를 추가하면 회문 cbabc가됩니다)
입력 : s = 아바
출력: 1 (앞면을 추가하면 회문 aabbaa가 됨)
간단한 방법
암호알고리즘
- 길이가 L 인 문자열 s를 초기화합니다.
- 개수와 플래그 변수를 저장할 정수 변수를 만듭니다. 두 변수를 모두 0으로 초기화합니다.
- 길이가 0보다 큰 동안 문자열을 탐색합니다. 문자열을 탐색하고 문자열 중간에 도달 할 때까지 시작 문자를 끝 문자와 비교하기 시작합니다. 현재 문자열이 회 문인 경우, 즉 시작 문자가 끝 문자와 같으면 플래그 변수를 1로 업데이트하고 루프를 중단합니다.
- 그렇지 않으면 count 변수를 1 씩 증가시키고 문자열의 마지막 문자를 제거합니다.
- 플래그 변수가 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) 우리는 일정한 추가 공간을 사용했기 때문에
효율적인 방법
암호알고리즘
- 길이가 L 인 문자열 s를 초기화합니다.
- 문자열 변수를 만들고 그 안에 원래 문자열의 반대를 저장합니다.
- 문자열의 연결을 저장하고 그 사이에 특수 문자가있는 원래 문자열과 반전 된 문자열의 연결을 저장하는 다른 문자열을 작성하십시오.
- lps 배열을 초기화합니다.
- 문자열을 탐색하고 lps 배열의 값을 업데이트합니다.
- 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).
