最大匹配字符串

Question

我想寫一個方法，將返回一個代碼對應於我需要傳遞給Web服務的銀行產品。我有一系列合格的通用類型的產品，輸入將是一個字符串，它將成爲數組中任何通用類型的特定類型。讓我通過我已經有的代碼來解釋：

public static void main(String[] args) 
{ 
    String[] names = { "Checking", "Savings", "DEMAT", "DEMAT Savings", "Interest Checking" }; 
    String input = "Employee Checking"; 
    int min = Integer.MAX_VALUE; 
    String maxMatch = null; 
    for(String name : names) 
    { 
     int i = input.indexOf(name); 
     if(i > -1 && i < min) 
     { 
     min = i; 
     maxMatch = name; 
     } 
    } 
    if(null != maxMatch) 
    { 
     System.out.println("Maximum match for " + input + " found at " + maxMatch); 
    } 
} 

上面的代碼片段試圖執行輸入的最大匹配。因此，如果我有「員工利益檢查」作爲輸入，我會在「利息檢查」中獲得匹配，而不僅僅是「檢查」。

我想知道的是，是否有任何方法可以進一步優化此代碼段，或者是否存在代碼失敗的情況？

Answer 1

如果你保持有序陣列由字符串的長度，你可以肯定的是第一場比賽將給予最大匹配

import java.util.Arrays; 
import java.util.Comparator; 

public class MaxIndex { 

private static String[] names = { "Checking", "Savings", "DEMAT", "DEMAT Savings", 
     "Interest Checking","Savings Interest Checking","My Employee Savings Interest Checking" }; 

public static void main(String[] args) { 

    Arrays.sort(names, new Comparator<String>() { 

     @Override 
     public int compare(String o1, String o2) { 
      Integer L1 = o1.length(); 
      return L1.compareTo(o2.length())*-1; 
     } 
    }); 

    findMaxMatch("Employee Checking"); 
    findMaxMatch("Employee Savings"); 
    findMaxMatch("Employee Interest Checking"); 
    findMaxMatch("Employee Savings Interest Checking"); 
    findMaxMatch("My Employee Savings Interest Checking"); 
    findMaxMatch("Employee Current"); 
} 

private static void findMaxMatch(String input) { 
    String maxMatch = maxMatch(input); 
    if (null != maxMatch) { 
     System.out.println("Maximum match for '" + input + "' found at '" 
       + maxMatch+"'"); 
    }else{ 
     System.out.println("No match for '"+input+"'"); 
    } 
} 

private static String maxMatch(String input) { 
    for (String name : names) { 
     int i = input.indexOf(name); 
     if (i > -1) { 
      return name; 
     } 
    } 
    return null; 
} 

}

輸出

Maximum match for 'Employee Checking' found at 'Checking' 
Maximum match for 'Employee Savings' found at 'Savings' 
Maximum match for 'Employee Interest Checking' found at 'Interest Checking' 
Maximum match for 'Employee Savings Interest Checking' found at 'Savings Interest Checking' 
Maximum match for 'My Employee Savings Interest Checking' found at 'My Employee Savings Interest Checking' 
No match for 'Employee Current' 

Answer 2

如果最大匹配不在字符串的第一部分，則會失敗。例如，如果您的輸入是Interest Checking For Employees，它將匹配Checking而不是Interest Checking。最大匹配是否應該找到匹配最多的順序字符的帳戶？或者只是最接近輸入結尾的比賽？

Answer 3

使用這種尋找最後的位置

names.lastIndexOf(input) 

基於陣列的位置，獲得的價值

Answer 4

如果我理解你的問題正確，你想找到的情況下有多個匹配的最長匹配。一種方法是按照降序排列你的「名字」（根據他們的長度），並在第一場比賽中停下來。

您可以通過在你把每一個「名」的長度從你的「名稱」爲關鍵字的的SortedMap <整數，字符串>做到這一點。

例如，通過做這樣的事情：

SortedMap<Integer,String> map = new TreeMap<Integer, String>(new Comparator<Integer>() { 
    public int compare(Integer o1, Integer o2) { 
     return -o1.compareTo(o2); 
    } 
}); 
for (final String name: names) { 
    map.put(name.length(),name); 
} 

然後迭代和你找到的第一個匹配就立即停止。

這有點「過度殺傷力」，但它的工作原理。

Answer 5

如果我沒有理解你是否正確，找到的字符串總是應該是查詢的子字符串？

使用找到一個子字符串，如果找到了，如果它是最長的還保留它。

public static void main(String[] args) 
{ 
    String[] names = {"Checking", "Savings", "DEMAT", "DEMAT Savings", "Interest Checking"}; 
    String input = "Employee Interest Checking"; 
    int min = Integer.MIN_VALUE; 
    String maxMatch = null; 
    for (String name : names) 
    { 
     boolean has = input.contains(name); 
     if (has && min < name.length()) 
     { 
      min = name.length(); 
      maxMatch = name; 
     } 
    } 
    if (null != maxMatch) 
    { 
     System.out.println("Maximum match for " + input + " found at " + maxMatch); 
    } 
} 

就像user988052說的那樣;如果您以正確的方式訂購陣列，您可以在第一場比賽中停止，因此您不必再搜索並可以消除min。

訂購陣列由長度降序：

Arrays.sort(names, new Comparator<String>() 
    { 
     public int compare(String o1, String o2) 
     { 
      int d = o2.length() - o1.length(); 
      return d != 0? d : ((Comparable<String>)o1).compareTo(o2); 
     } 
    });