[leetcode-214]Shortest Palindrome(java)
3665 단어 leetcode
For example:
Given “aacecaaa”, return “aaacecaaa”.
Given “abcd”, return “dcbabcd”.
분석: 이 문 제 는 제 생각 이 비교적 간단 합 니 다. 답문 을 보완 하려 면 중간 부터 효과 적 인 구조 답문 의 접경 점 인지 판단 하 세 요.그렇지 않다 면 base –, 여기 서 주의해 야 할 것 은 모든 base 에 있어 두 가지 가능성 이 있 습 니 다. 하 나 는 홀수 형 이 고, 다른 하 나 는 짝수 형 입 니 다.이런 방법 은 시간 복잡 도 는 O (n2) 이 고 O (n) 의 해결 방안 도 있 으 며 사용 하 는 Manacher 알고리즘 이 라 고 합 니 다.
운행 시간: 336 ms
public class Solution {
public String shortestPalindrome(String s) {
char[] chars = s.toCharArray();
if(chars.length<=0)
return "";
int length = chars.length;
int base = (length-1)/2;
boolean isOdd = true;
while (base>=0){
if(isValid(chars,base,base+1)) {
isOdd = false;
break;
}
if(isValid(chars,base,base))
break;
base--;
}
StringBuilder builder = new StringBuilder();
int index = length-1;
while(index>=base){
builder.append(chars[index--]);
}
int oneSize = builder.length();
if(isOdd)//
index = oneSize-2;
else{
builder.deleteCharAt(oneSize-1);
index = oneSize-2;
}
while(index>=0)
builder.append(builder.charAt(index--));
return builder.toString();
}
private boolean isValid(char[] chars,int left,int right){
while(left>=0){
if(right>=chars.length || chars[left]!=chars[right])
return false;
left--;right++;
}
return true;
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
