매일 알고리즘 면접 문제 (6): leetcode 214 최 단 답장 꼬치

제목: 문자열 s 를 지정 합 니 다. 문자열 앞 에 문 자 를 추가 하여 답장 문자열 로 변환 할 수 있 습 니 다.이런 방식 으로 변환 할 수 있 는 가장 짧 은 답장 열 을 찾 아서 되 돌려 줍 니 다.
예시 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;
    }

만약 당신 이 의문 이나 더 좋 은 알고리즘 사고방식 이 있다 면, 댓 글 교 류 를 환영 합 니 다!!