题目:
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。
在构造过程中,请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。
示例 1:
输入:
"abccccdd"
输出:
7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
题解:
方案一:使用ASCII表,英文字母大小写总共占有58个字符,统计字符串中的每个字符出现的次数,放在数组中,再判断每个字符出现的次数有多少个2的倍数,再乘以2,最后求和;如果字符是奇数个,那么再加1。
方案二:使用map,原理同上,只是将数组换成hashMap.
scala代码:
/**
* 使用ASCII表方式
*
* @param s
* @return
*/
def longestPalindrome(s: String): Int = {
val arr = new Array[Int](58)
//对于字符串中的每一个字符,在数组中值变为1,没有的字符为0
for (i <- 0 until s.length) {
arr(s.charAt(i) - 'A') = arr(s.charAt(i) - 'A') + 1
}
var count = 0
for (num <- arr) {
count = count + num / 2 * 2
//如果字符个数为奇数,在计算count最后加上1
if (num % 2 == 1 && count % 2 == 0) {
count = count + 1
}
}
count
}
/**
* 借助map来实现
*
* @param s
* @return
*/
def longestPalindrome2(s: String): Int = {
val map = new mutable.HashMap[Char, Int]()
for (char <- s.toCharArray) {
map.put(char, map.getOrElse(char, 0) + 1)
}
var count = 0
for (num <- map.values) {
count = count + num / 2 * 2
//如果字符个数为奇数,在计算count最后加上1
if (num % 2 == 1 && count % 2 == 0) {
count = count + 1
}
}
count
}