매일 알고리즘 면접 문제 (6): leetcode 214 최 단 답장 꼬치
2848 단어 면접 문제알고리즘 문제프로 그래 밍 학습
예시 1:
: "aacecaaa"
: "aaacecaaa"
예시 2:
: "abcd"
: "dcbabcd"
알고리즘 사고: 매일 알고리즘 면접 문제 (5) 를 참고 하 십시오. leetcode 5 의 가장 긴 답장 문자열 에서 가장 긴 답장 문자열 의 사 고 를 찾 습 니 다. 먼저 문자열 중의 가장 큰 답장 문자열 을 찾 습 니 다. 이 를 바탕 으로 최대 답장 문자열 의 왼쪽 이나 오른쪽 에 문 자 를 추가 하여 이 를 만 드 는 답장 문자열 이 가장 짧 은 답장 문자열 입 니 다.제목 은 문자열 앞 에 문 자 를 추가 해 야 하기 때 문 입 니 다. 즉, 찾 은 최대 답장 문자열 에 포 함 된 왼쪽 문자열 의 문자 수 는 오른쪽 문자열 의 수량 보다 많 습 니 다. 그렇지 않 으 면 오른쪽 에서 보완 해 야 합 니 다. 그리고 왼쪽 첫 번 째 문 자 를 포함해 야 합 니 다.첫 번 째 문자 가 포함 되 지 않 으 면 문자열 오른쪽 에 해당 하 는 위치 에서 이 문 자 를 고 쳐 야 하기 때문에 최대 답장 문자열 의 중심 점 은 문자열 의 왼쪽 이나 중심 위치 에 있 고 첫 번 째 문 자 를 포함 해 야 합 니 다. 즉, 왼쪽 에서 반 문자열 의 길 이 를 옮 겨 다 니 며 첫 번 째 문 자 를 포함 하 는 가장 긴 답장 문자열 을 찾 아야 합 니 다.
알고리즘 코드: 알고리즘 사고방식 에 따라 쓴 알고리즘 의 구체 적 인 코드 는 다음 과 같다.
public String shortestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
int len = s.length();
int maxLength = 0;
int maxStart = 0;
int maxEnd = 0;
for(int i = 0; i <= len / 2; i ++) {
int findLen1 = expandAroundCenter(s, i, i); // “aba”
int findLen2 = expandAroundCenter(s, i, i + 1); // “cbbc”
int findLen = Math.max(findLen1, findLen2);
int finStart = i - (findLen - 1) / 2;
if (findLen > maxLength && finStart == 0) {
maxLength = findLen;
maxStart = 0;
maxEnd = i + findLen / 2;
}
}
String needAdd;
if (maxStart == 0 && len > 1) {
needAdd = s.substring(maxEnd + 1);
} else if (len > 1){
needAdd = s.substring(1);
} else {
needAdd = null;
}
if (needAdd != null && needAdd.length() > 0) {
StringBuilder stringBuilder = new StringBuilder();
for (int i = needAdd.length() - 1; i >= 0; i --) {
stringBuilder.append(needAdd.charAt(i));
}
stringBuilder.append(s);
return stringBuilder.toString();
}
return s;
}
// :
public int expandAroundCenter(String s, int left, int right) {
int len = s.length();
while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
left --;
right ++;
}
if (left < 0 || right >= len || s.charAt(left) != s.charAt(right)) {
left ++;
right --;
}
return right - left + 1;
}
만약 당신 이 의문 이나 더 좋 은 알고리즘 사고방식 이 있다 면, 댓 글 교 류 를 환영 합 니 다!!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Java 프로그래머 면접에서의 다중 스레드 문제 요약wait ()/notify ()/notify All () 의 모든 방법을 호출할 때, 현재 라인이 이 대상의 자물쇠를 얻지 못하면, Illegal MonitorState Exception의 이상을 던집니다. Thre...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.