java - 如何找到给定字符串中的每个回文子字符串并在一秒钟内返回一个出现值
问题描述
我一直在努力解决如下问题:
给你一串小写拉丁字母。让我们将子字符串的“出现值”定义为字符串中子字符串出现的次数乘以子字符串的长度。对于给定的字符串,找到回文子串的最大出现值。
我的代码运行良好,但是,对于最多 300 000 个字符的输入,我需要在一秒钟内获得解决方案。到目前为止,我的代码如下:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
public class Palindrome {
public static void main(String[] args) {
// initiate a scanner
Scanner in = new Scanner(System.in);
String pal = in.nextLine();
getAllPalindrome(pal);
}
/**
* checks if the given string is a palindrome
*
* @param pal
* @return
*/
public static boolean checkPalindrome(String pal) {
for (int i = 0; i < pal.length() / 2; i++) {
if (pal.charAt(i) != pal.charAt(pal.length() - 1 - i)) {
return false;
}
}
return true;
}
/**
* gets all palindromes
*
* @param pal
*/
public static void getAllPalindrome(String pal) {
// initiate variables
ArrayList<String> pals = new ArrayList<String>();
int count = 0;
// add all palindromes to an arraylist
for (int i = 0; i < pal.length(); i++) {
for (int j = i; j < pal.length(); j++) {
if (checkPalindrome(pal.substring(i, j + 1))) {
pals.add(pal.substring(i, j + 1));
}
}
}
int[] counts = new int[pals.size()];
for (int i = 0; i < pals.size(); i++) {
int lCount = 0;
String j = pals.get(i);
for (int k = 0; k < pals.size(); k++) {
if (j.equals(pals.get(k))) {
lCount += 1;
}
counts[i] = lCount * pals.get(i).length();
}
}
int hov = 0;
for (int i = 0; i < pals.size(); i++) {
if (counts[i] > hov) {
hov = counts[i];
}
}
System.out.println(hov);
}
}
解决方案
你只需要稍微重构你的代码。
- 首先,您必须收集所有独特的回文并计算每个回文在字符串中出现的次数。
- 遍历地图并增加回文长度和它的出现(即找到每个唯一回文的总长度)。
- 检索最大值。
public class Palindrome {
public static void main(String[] args) {
try (Scanner scan = new Scanner(System.in)) {
System.out.println(getMaxOccurrenceValue(scan.nextLine()));
}
}
/** Retrieve maximum occurrence value */
public static int getMaxOccurrenceValue(String pal) {
return getAllPalindromes(pal).entrySet().stream()
.map(entry -> entry.getKey().length() * entry.getValue())
.mapToInt(Integer::intValue)
.max().orElse(0);
}
/** Retrieve all unique palindromes for given str with occurrence amount of each palindrome */
private static Map<String, Integer> getAllPalindromes(String str) {
Map<String, Integer> map = new TreeMap<>();
for (int i = 0; i < str.length(); i++) {
for (int j = i + 1; j < str.length(); j++) {
String sub = str.substring(i, j);
if (isPalindrome(sub))
map.compute(sub, (key, count) -> Optional.ofNullable(count).orElse(0) + 1);
}
}
return map;
}
/** Check is given str palindrome or not */
private static boolean isPalindrome(String str) {
for (int i = 0, j = str.length() - 1; i < j; i++, j--)
if (str.charAt(i) != str.charAt(j))
return false;
return true;
}
}
推荐阅读
- nginx - 如何在nginx中进行长时间缓存?
- r - ggplot2 删除绘图周围的外边框
- javascript - 带有按键输入的js问题不发送文本
- json - Swift:无法读取数据,因为它的格式不正确
- aws-lambda - 使用 Amazon Lex 暂停用户
- java - 如何交换文件中两行的位置Java直接访问这些行
- eclipse - 使用 Maven 作为代理/VPN,Maven 不下载任何文件
- opencv - 告诉图书馆创建球形全景图
- java - 模块化 Spring Boot 2 应用程序导致集成测试失败
- mysql - 从另一个表返回单个记录,每个 transactionDate 有多个记录