最佳搜索字符串中的子字符串java

我有一个电话号码列表，其中可能包含或不包含国家代码。我从后台服务获取一个始终包含国家代码的号码。因此，我最佳地找到了与来自后端服务的号码匹配的号码。最佳搜索字符串中的子字符串java

现在我正在做的事情是：

for(String number : backendNumbers){ 
    for(Map.Entry<String, String> entry : contactMap.entrySet()){ 
     if(number.endsWith(entry.getKey()) && entry.getKey().length() > MINIMUM_CONTACT_LENGTH){ 
      Log.i(TAG, "Found name for "+entry.getKey()+" : "+entry.getKey()+":"+entry.getValue()); 
      break; 
     } 
    } 
}

凡接触的地图是地图这样的接触= <“01710111111”，“有些名”> - >该项可能会或可能不会包含国家代码。在大多数情况下，他们没有。

当我从后端一些总是包含这样的国家代码：“8801710111111”。

现在，这种方法的问题是有生成每次我需要地图的接触地图的开销。同样在我从后端得到N个号码的情况下，我需要遍历整个联系地图，以找到名称。

那么我在这里可以做得更好吗？任何建议将不胜感激。

来源

2017-08-27 Shaheed

对于给定的循环代码，你可以转移到map.keySet()只处理字符串键。否则这种方法没有错，这是您在比较hashmap值时需要的最小开销。

来源

2017-08-27 10:26:04

现在，这种方法的问题是每次我需要该地图时都会生成联系地图的开销。

那么，要么你有一些结构，以方便搜索或通过整个列表搜索。

我想创建数量的Map<String, String>来命名。创建地图时还要计算编号为minLength的最小长度。

然后，给后端数，查找不只是数量，而且所有后缀高达minLength长度。

for (int beginIndex = 0; beginIndex <= (backendNumber.length() - minLength); beginIndex++) { 
    String name = nameByNumber.get(backendNumber.substring(beginIndex)); 
    if (name != null) { 
     return name; 
    } 
}

这会给你类似于O（最大长度的后端号码 - 最小号码长度）的复杂性。

来源

2017-08-27 10:36:26 lexicore

假设两个集合都大了，下面可能获得10倍：

for (char c='0'; c<='9'; ++c) { 
    Map<String, String> submap = new Map<>(); 
    for(Map.Entry<String, String> entry : contactMap.entrySet()) { 
     String key = entry.getKey(); 
     if (key.length() > MINIMUM_CONTACT_LENGTH 
       && key.charAt(key.length() - 1) == c) { 
      submap.put(key, entry.getValue()); 
     } 
    } 
    for(String number : backendNumbers){ 
     if (!number.isEmpty() 
       && number.charAt(number.length() - 1) == c) { 
      for(Map.Entry<String, String> entry : submap.entrySet()) { 
       .... do what you did 
      } 
     } 
    } 
}

的想法很简单：一个字符串只能是一个又一个的子串，如果两端具有相同的字符。因此，我相应地分割了两个集合，并将诸如xxxxx1之类的测试保存为xxxxx2。

很明显，你可以使用，而不是最后两个数字，但是这增加了更多的开销。原来的复杂度是O(m*n)，这个技巧是O((m+n)*k + (m/k)*(n/k))，其中k是桶的数量。我假设最后一位数字是均匀分布的，这通常是。

它可以做的更好....

来源

2017-08-27 11:00:23 maaartinus

您可以创建一个地图有和没有国家代码backendnumbers的（是不是总是3个字符？）

Map<String,String> backendMap = new HashMap<>(); 
for(String number : backendNumbers){ 
    backendMap.put(number,number); 
    backendMap.put(number.substring(3),number); 
}

那么你可以做一个简单的坐上backendMap找到（或未找到）的数量（假设号码的国家代码总是以相同的形式）。

来源

2017-08-27 11:03:50 Turo

不要遗憾的是，国家代码并不总是3个字符，它可以是1,2,3或4个字符。 – Shaheed

最佳搜索字符串中的子字符串java

回答

相关问题