查找两个候选字符串列表之间的交集

Question

我编写了以下Java代码，找到Java的prefix和suffix的String之间的交集。

// 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。有人能帮我弄清楚我做错了什么吗？

Answer 1

我会写你的方法如下：

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(); 

Answer 2

我看到@ted跳转的代码很好.. 该问题指定返回给定String的后缀和前缀中匹配字符的最大数量，该字符串是一个合适的子集。因此，整个字符串不考虑这个最大数量。

Ex。 “abbabba”，前缀和后缀可以有abba（前4个字符） - abba（后4个字符），因此编码的长度，前缀（c，co，cod，codi，co ...），sufix （y，ty，ity，lity ....），它们都不相同。这里 因此长度为0

通过从

if (prefix.equals(suffix)) { 
    ++count; 
} 

与

if (prefix.equals(suffix)) { 
    count = prefix.length();// or suffix.length() 
} 

我们得到的最大长度在这里修改计数。 但是这可以在O（n）中完成..字符串的内置函数等于，我相信会花费O（n），因此整体复杂度为O（n2）.....

Answer 3

我会使用此代码。

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; 
} 

Answer 4

@ ravi.zombie 如果您需要为O（n）的长度，那么你只需要如下改变泰德的代码：

int max =0; 
for (int i = 1; i <= len-1; ++i) { 
    final String prefix = s.substring(0, i); 
    final String suffix = s.substring(len - i, len); 
    if (prefix.equals(suffix) && max < i) { 
     max =i; 
} 
    return max; 
} 

我也离开了整个字符串比较来获得正确的前缀和后缀，所以这应该返回4而不是7输入字符串abbabba。