java如何找到给定字符串中的每个回文子字符串,并在不到一秒钟的时间内返回一个出现值
我一直在努力解决以下问题:
You are given a string of lower-case Latin letters. Let us define a substring's "occurrence value" as the number of the substring occurrences in the string multiplied by the length of the substring. For a given string find the largest occurrence value of palindromic substrings.
我的代码工作得很好,但是,我需要在不到一秒钟的时间内输入多达30万个字符的解决方案。我的代码如下:
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);
}
}
# 1 楼答案
你只需要稍微重构一下你的代码