查找兩個候選字符串列表之間的交集

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。