leetcode 214: Shortest Palindrome
Total Accepted: 172
Total Submissions: 1344
Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
For example:
Given
"aacecaaa" , return "aaacecaaa" . Given
"abcd", return "dcbabcd". [사고방식]어떤 char 부터 양쪽 으로 확장 (좌우 양쪽 문자 가 같 음) 합 니 다. 문자열 의 머리 까지 확장 할 수 있다 면 끝 에 남 은 reverse 를 원래 문자열 의 머리 에 추가 하면 됩 니 다.
tips: 1. 중축 문 자 는 중간 부터 선택 합 니 다. 이렇게 찾 은 것 이 가장 짧 은 것 입 니 다. 2. 중축 문 자 는 하나 일 수도 있 고 두 개 일 수도 있 습 니 다.
[CODE]
public class Solution {
public String shortestPalindrome(String s) {
if(s.length()<=1 ) return s;
int center = (s.length()-1)/2;
String res="";
for(int i=center; i>=0; i--) {
if(s.charAt(i) == s.charAt(i+1)) {
if( (res = check1(s, i, i+1)) !=null) return res;
}
if( (res = check1(s, i, i)) !=null) return res;
}
return res;
}
//aabaac
private String check1(String s, int l, int r) {
int i=1;
for(; l-i>=0 && r+i<s.length(); i++) {
if(s.charAt(l-i) != s.charAt(r+i) ) break;
}
if(l-i>=0) return null;
StringBuilder sb = new StringBuilder(s.substring(r+i));
sb.reverse();
return sb+s;
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
