java查找两个候选字符串列表之间的交集
我编写了下面的Java
代码,以查找prefix
和suffix
中String
的Java
之间的交集
// you can also use imports, for example:
// import java.math.*;
import java.util.*;
class Solution {
public int max_prefix_suffix(String S) {
if (S.length() == 0) {
return 1;
}
// prefix candidates
Vector<String> prefix = new Vector<String>();
// suffix candidates
Vector<String> suffix = new Vector<String>();
// will tell me the difference
Set<String> set = new HashSet<String>();
int size = S.length();
for (int i = 0; i < size; i++) {
String candidate = getPrefix(S, i);
// System.out.println( candidate );
prefix.add(candidate);
}
for (int i = size; i >= 0; i--) {
String candidate = getSuffix(S, i);
// System.out.println( candidate );
suffix.add(candidate);
}
int p = prefix.size();
int s = suffix.size();
for (int i = 0; i < p; i++) {
set.add(prefix.get(i));
}
for (int i = 0; i < s; i++) {
set.add(suffix.get(i));
}
System.out.println("set: " + set.size());
System.out.println("P: " + p + " S: " + s);
int max = (p + s) - set.size();
return max;
}
// codility
// y t i l i d o c
public String getSuffix(String S, int index) {
String suffix = "";
int size = S.length();
for (int i = size - 1; i >= index; i--) {
suffix += S.charAt(i);
}
return suffix;
}
public String getPrefix(String S, int index) {
String prefix = "";
for (int i = 0; i <= index; i++) {
prefix += S.charAt(i);
}
return prefix;
}
public static void main(String[] args) {
Solution sol = new Solution();
String t1 = "";
String t2 = "abbabba";
String t3 = "codility";
System.out.println(sol.max_prefix_suffix(t1));
System.out.println(sol.max_prefix_suffix(t2));
System.out.println(sol.max_prefix_suffix(t3));
System.exit(0);
}
}
一些测试用例包括:
String t1 = "";
String t2 = "abbabba";
String t3 = "codility";
预期值为:
1, 4, 0
我的想法是产生prefix
候选并将其推入向量,然后找到suffix
候选并将其推入vector
,最后将两个vectors
推入Set
并计算差异。然而,我得到了1, 7, and 0
。有人能帮我弄清楚我做错了什么吗
# 1 楼答案
我会使用这个代码
# 2 楼答案
@ravi。僵尸 如果您需要O(n)的长度,则只需更改Ted的代码,如下所示:
为了得到正确的前缀和后缀,我还省略了整个字符串比较,所以对于输入字符串abba,应该返回4而不是7
# 3 楼答案
我看到@ted Hop的代码很好。。 问题指定返回给定字符串的后缀和前缀中匹配字符的最大数量,这是一个适当的子集。因此,这个最大值不考虑整个字符串
例如,“abba”,前缀和后缀可以有abba(前4个字符)-abba(后4个字符),因此长度为4 编码能力,前缀(c,co,cod,codi,co…),,苏菲克斯(y,ty,ity,ty…),它们都不一样。 因此这里的长度是0
通过修改这里的计数
与
我们得到了最大长度。 但这能在O(n)。。string equals的内置函数,我相信会取O(n),因此整体复杂度为O(n2)
# 4 楼答案
我会把你的方法写如下:
如果需要将前缀与后缀的反向进行比较,我会这样做: