주어진 문자열을 회문으로 변환하는 방법은 무엇입니까?

Question

내가는 인터뷰 질문했다 : "회문에 주어진 문자열로 변환 출력 (회문 문자열) 지정된 캐릭터 라인의 문자열이 포함되어야 제공"

을 그래서

를 I 이런 식으로, root 주어진 입력으로 그 문자열의 반전을 발견하고 주어진 입력에 추가합니다. 그래서 문자열을 얻을 :

roottoor 

회문이다

또한 내가/P (root)가 오/피에 존재하는이 포함되어 있습니다.

이 솔루션을 사용하면 최적의 솔루션이 아니라 최적의 솔루션을 제공 할 수 있습니까?

나는 이것에서 어떤 것도 찾을 수 없었다.

다른 해결책이 있습니까?

그는 자바로 할 필요가 있다고 말했다.

Answer 1

주어진 문자열의 경우 s 인 경우 s의 끝에있는 가장 긴 하위 문자열 s1을 이미 회문문으로 찾으십시오. 그런 다음 끝에 s\s1의 역순으로 붙여주십시오. 방금 "lamb"의 반대를 추가 할 수 있도록

예를 들어, 입력 문자열 "lambada"을 위해, "ada"는 회문이며, 결과는 "lambadabmal"입니다.

편집 :, 당신은 또한 반대 방향을 확인하고 짧은 회문을 초래 하나를 선택해야 maartinus '대답을 고려 : 주어진 문자열 s를 들어

을의 시작 부분에 가장 긴 문자열 s1을 찾을 수 s은 이미 회문입니다. 그런 다음 처음에 s\s1의 역순을 삽입하기 만하면됩니다. 당신은 단지 시작에 "fat"의 반대를 삽입 할 수 있도록

예를 들어, 입력 문자열 "arafat" 위해, "ara"는 회문이며, 결과는 "tafarafat"입니다.

Answer 2

다른 대답은 처음에는 분명히보고 싶지 않습니다. 예

racecars -> racecarsracecar // when only the end is considered 

racecars -> sracecars  // when the start is considered 

그냥 양끝을보고 더 나은 결과를 반환하십시오. 마지막 문자 다음의 중심, 즉 수있는 바와 같이, 단지, 처음 n-1 문자를 추가하려면