首页 > 代码库 > leetcode409
leetcode409
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.
Input:"abccccdd"Output:7Explanation:One longest palindrome that can be built is "dccaccd", whose length is 7.
寻找字符串重组之后能存在的最长的回文串。
思路清晰:
用数组记录出现相同字符的个数,只要个数大于2个那么一定能在最后的回文串中出现,如果有单个的只能最多增加以一个长度。
public class Solution { public int longestPalindrome(String s) { int[] str = new int[123]; for (int i=0;i<s.length();i++){ str[s.charAt(i)]++; } int flag = 0; int sum = 0; for (int i=65;i<=90;i++){ if(str[i] > 1){ sum += str[i]; if(str[i]%2 != 0){ flag = 1; sum--; } }else if (str[i] == 1) flag = 1; } for (int i=97;i<=122;i++){ if(str[i] > 1){ sum += str[i]; if(str[i]%2 != 0){ flag = 1; sum--; } }else if (str[i] == 1) flag = 1; } return sum + flag; }}
然后根据高手提示,还可以少很多代码,如果最后的回文串长度小于原来的长度,直接加一就可以了,如果和原来相同则不加,因为多余下来的只能有一个字符处于最后回文串的中间位置。
更改后代码是这样的。
public class Solution { public int longestPalindrome(String s) { int[] str = new int[123]; for (int i=0;i<s.length();i++) str[s.charAt(i)]++; int sum = 0; for (int i=65;i<=122;i++) sum += str[i]/2; sum *= 2; if(sum < s.length()) return sum+1; else return sum; }}
leetcode409
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。