带字符的最长字符串回文
带字符的最长字符串回文
提问于 2018-06-03 14:42:54
来自学校作业的问题描述带有回文的最长字符串
我得到了复杂度O(N^2)。如何实现O(N*log(N))**
My code
int maxL = 0;
for (int i = 0; i < S.length(); i++) {
String currentString = String.valueOf(S.charAt(i));
for (int j = i + 1; j < S.length(); j = j + 1) {
String jStr = String.valueOf(S.charAt(j));
if (currentString.contains(jStr)) {
currentString = currentString.replace(jStr, "");
int len = j - i + 1;
if (currentString.length() == 0 && maxL < len) {
maxL = len;
}
} else {
currentString = currentString + jStr;
}
}
}
return maxL;回答 1
Stack Overflow用户
回答已采纳
发布于 2018-06-03 17:11:25
这个问题可以用O(n)空间在O(n)时间内解决。下面的算法使用一个位集来跟踪从给定字符串开头开始的子字符串的不平衡字符。它对字符串进行一次遍历，并记住它已经在散列映射中看到的状态。每当我们第二次看到相同的状态时，我们就找到了一个有效的密码:只需从当前子字符串的开头删除旧的较短的子字符串。
private static int index(char c) {
if (c < '0') throw new IllegalArgumentException("illegal char");
if (c <= '9') return c - '0';
if (c < 'a') throw new IllegalArgumentException("illegal char");
if (c <= 'z') return c - 'a' + 10;
throw new IllegalArgumentException("illegal char");
}
private static int solution(String s) {
HashMap<BitSet, Integer> states = new HashMap<>();
int longest = 0;
BitSet state = new BitSet();
states.put((BitSet) state.clone(), 0);
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
state.flip(index(c));
Integer seenAt = states.get(state);
if (seenAt != null) {
int len = i - seenAt + 1;
if (len > longest) longest = len;
} else {
states.put((BitSet) state.clone(), i + 1);
}
}
return longest;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50663924
复制相关文章
相似问题