leetcode409.Longest Palindrome

1588 단어 leetcode자바hash
제목 요구
Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

문자열 을 입력 하 십시오. 이 문자열 의 값 으로 가장 긴 회 수 를 구성 하 는 길이 가 얼마 인지 계산 하 십시오.
아이디어 와 코드
이것 은 easy 난이도 의 문제 이지 만 한꺼번에 쓰 는 것 도 도전 적 이다.직관 적 으로 보면 우 리 는 통계 문자열 에 있 는 모든 문자 가 나타 나 는 횟수 를 바로 생각 할 수 있다. 만약 에 이 문자 가 나타 나 는 횟수 가 짝수 라면 문 자 는 반드시 회수 에 존재 한다.그러나 우 리 는 문자 에 하나의 추가 문자 가 중간 에 있 으 면 이 문자열 도 회 수 를 구성 할 수 있다 는 점 을 무시 했다. 예 를 들 어 aabaa.이 세부 사항 은 주의해 야 한다.다음은 O (N) 시간의 실현:
    public int longestPalindrome(String s) {
        int[] count = new int[52];
        int max = 0;
        for(char c : s.toCharArray()) {
            if(c>='a' && c<='z'){
                count[c-'a']++;
                if(count[c-'a'] % 2 == 0) {
                    max +=2;
                }
            }
            
            if(c>='A' && c<='Z'){
                count[c-'A' + 26]++;
                if(count[c-'A'+26] % 2 == 0) {
                    max += 2;
                }
            }
        }
        
        if(max < s.length()) {
            max++;
        }
        return max;
    }

좋은 웹페이지 즐겨찾기