查找两个候选字符串列表之间的交集
查找两个候选字符串列表之间的交集
提问于 2012-11-05 01:14:57
我编写了以下Java代码，以便在Java中查找prefix和String的suffix之间的交集。
// 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。有人能帮我找出我做错了什么吗？
回答 4
Stack Overflow用户
发布于 2012-11-05 01:34:55
我会把你的方法写成如下：
public int max_prefix_suffix(String s) {
final int len = s.length();
if (len == 0) {
return 1; // there's some dispute about this in the comments to your post
}
int count = 0;
for (int i = 1; i <= len; ++i) {
final String prefix = s.substring(0, i);
final String suffix = s.substring(len - i, len);
if (prefix.equals(suffix)) {
++count;
}
}
return count;
}如果你需要比较前缀和后缀的反面，我会这样做：
final String suffix = new StringBuilder(s.substring(len - i, len))
.reverse().toString();Stack Overflow用户
发布于 2013-04-28 19:44:39
我看到@ted Hop编写的代码很好..问题指定返回给定字符串的后缀和前缀中匹配字符的最大数量，这是一个真的子集。因此，对于这个最大数字，不考虑整个字符串。
例如。"abbabba"，前缀和后缀可以具有abba (前4个字符)-abba(最后4个字符)，因此长度为4 codility，，prefix(c，co，cod，codi，co...)，，sufix (y，ty，ity，ly...)，它们都不相同。因此这里的长度是0。
通过修改此处的计数
if (prefix.equals(suffix)) {
++count;
}使用
if (prefix.equals(suffix)) {
count = prefix.length();// or suffix.length()
}我们得到最大长度。但这能在O(N)中完成吗？字符串的内置函数等于，我相信将花费O(n)，因此总体复杂度为O(n2).....
Stack Overflow用户
发布于 2013-07-24 21:26:46
我会使用下面的代码。
public static int max_prefix_suffix(String S)
{
if (S == null)
return -1;
Set<String> set = new HashSet<String>();
int len = S.length();
StringBuilder builder = new StringBuilder();
for (int i = 0; i < len - 1; i++)
{
builder.append(S.charAt(i));
set.add(builder.toString());
}
int max = 0;
for (int i = 1; i < len; i++)
{
String suffix = S.substring(i, len);
if (set.contains(suffix))
{
int suffLen = suffix.length();
if (suffLen > max)
max = suffLen;
}
}
return max;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/13220887
复制相关文章
相似问题
腾讯云开发者
