6
\$\begingroup\$

I have a hash map which maps to some strings which serve as prefixes and are of small length (max length is 6):

Map<String, String> map = new HashMap<>();  
map.put("codeA", "100");  
map.put("codeB", "7");  
map.put("codeC", "0012");  
etc  

This is fine so far, but I also need when provided an input string to actually break it into 2 parts if the string has a prefix that matches one of the values in my map.

What I do is:

boolean found = false;  

String [] result;  
for(Entry<String, String> e: map.entrySet()) {  
   String code = e.getKey();  
   String value = e.getValue();  
   if(value.length >= inputString.length) continue;    
   if(inputString.startsWith(value)) {  
       result = new String[2];  
       result[0] = value;  
       result[1] = inputString.substring(value.length + 1);  
       found = true;  
       break;  
     }  
}    
return result;

Could this be improved? Could I have been using some additional datastructure/API for this?

I am interested in an approach in Java 7 without any extra libs. The HashMap has ~400 entries and the input string 8-11 characters.

I would need a way to get the prefix having the code (hence the HashMap) and break the input string into the prefix and the rest part.

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! Good job on your first question. \$\endgroup\$ – SirPython Oct 31 '15 at 0:25
  • \$\begingroup\$ One interesting test set from Tom Anderson's comment: "pot" and "potash" in set; query "potato". \$\endgroup\$ – greybeard Mar 8 at 7:45
  • \$\begingroup\$ Java 7 without any extra libs does this rule out open coding / roll-your-own? \$\endgroup\$ – greybeard Mar 8 at 7:48
  • \$\begingroup\$ (Just out of curiosity: why inputString.substring(value.length + 1)? Doesn't that mean inputString.equals(result[0] + result[1]) is false?) \$\endgroup\$ – greybeard Mar 8 at 7:55
2
\$\begingroup\$

Since you don't care about the keys and just want to match the values, you can use a NavigableSet (such as a TreeSet) of values:

NavigableSet<String> prefixes = new TreeSet<>(map.values());

String prefix = prefixes.floor(inputString);

if (prefix != null && inputString.startsWith(prefix)) {
    return new String[] {prefix, inputString.substring(prefix.length())};
} else {
    return null;  // or whatever you want to return if there's no match
}    
\$\endgroup\$
  • \$\begingroup\$ But my prefix match is on the values not on the keys \$\endgroup\$ – Jim Oct 7 '15 at 7:54
  • \$\begingroup\$ I missed that. Just make the TreeMap an inverse of the other one. In fact, since you don't care about the key, you can use a TreeSet instead. I will adjust the answer \$\endgroup\$ – Misha Oct 7 '15 at 7:56
  • \$\begingroup\$ So basically this way I would do O(logN) searches to find the floor and then an extra compare. My concern is that because it is a tree, it will be slower due to hitting random pages following the links in memory and might be more space demanding. \$\endgroup\$ – Jim Oct 7 '15 at 18:03
  • 1
    \$\begingroup\$ If your key is "potato", and your map contains "pot" and "potash", this won't work. It should find "pot" as a prefix, but "potash" is the last key before "potato". However, it will work if no prefix is ever a prefix of another prefix. \$\endgroup\$ – Tom Anderson Mar 14 '18 at 17:04
  • 1
    \$\begingroup\$ This one doesn't work. \$\endgroup\$ – Stefan Reich Mar 7 at 23:10
5
\$\begingroup\$

Trie

A trie would solve this problem perfectly. With a trie, you could search all your prefixes in \$O(n)\$ time, where \$n\$ is the length of the input string. You current implementation requires \$O(m*n)\$ time, where \$m\$ in the number of prefixes and \$n\$ is the length of the input string.

Of course, the trie solution will be much more complex than your existing solution, so you will need to weigh the performance benefits of using a trie versus the simplicity of using a HashMap.

\$\endgroup\$
  • \$\begingroup\$ The hash table has at max 400 entries and the input string is not more than 11 character. Is there any actual benefit in implementing a trie (and testing it etc) for my specific input? \$\endgroup\$ – Jim Oct 6 '15 at 20:31
  • \$\begingroup\$ Also I think that would mean that I would need 2 data structures in place. Both the hashmap and the trie, because I also need for other use cases the value in the hashmap given the code/key. Because I can't do that with the trie, right? \$\endgroup\$ – Jim Oct 6 '15 at 20:33
  • \$\begingroup\$ @Jim 1) For 400 entries, the performance benefit of a Trie would be small. Still, it depends on how many searches you plan on doing. If it is millions, you might want to try it. 2) You haven't shown the other use cases, so I don't know whether you still need the HashMap. You can use your Trie to search for key/value pairs. \$\endgroup\$ – JS1 Oct 6 '15 at 21:05
  • \$\begingroup\$ 1) The searches will be extremely few. But I am interested in speed nevertheless because the code will run in mobile device. 2) The 2 use cases is get the prefix having the code and breaking the input string to the prefix and the second part \$\endgroup\$ – Jim Oct 6 '15 at 21:29
  • 1
    \$\begingroup\$ @Jim I think that searching a HashMap of 400 entries will take less than 1 millisecond on a mobile device, so it's probably not going to be worth it. A trie can be modified to store a value per key like a Map, so if you did use the trie, it could be used to retrieve a code from a prefix. \$\endgroup\$ – JS1 Oct 7 '15 at 0:00
2
\$\begingroup\$

Misha's answer is on the right track - as far as i know, a NavigableSet is the best tool in the standard library. A trie would be perfect, but there isn't one!

However, it's not enough to just look for the lexicographically closest prefix, because there might be unrelated prefixes in between the true prefix and the search string. Consider the set of prefixes "pot" and "potash", and the input string "potato".

Instead, you have to find the closest prefix, and then walk backwards through the set of prefixes until you either find a match, or find something that can't possibly be a prefix. I think this should do it:

private String[] search(NavigableSet<String> prefixes, String inputString) {
    Iterator<String> it = prefixes.headSet(inputString, true).descendingIterator();
    while (it.hasNext()) {
        String prefix = it.next();
        if (inputString.startsWith(prefix)) return new String[]{prefix, inputString.substring(prefix.length())};
        else if (prefix.charAt(0) != inputString.charAt(0)) return null;
    }
    return null;
}

Although i have not tested this thoroughly.

\$\endgroup\$
  • \$\begingroup\$ I think this works, but it almost negates the whole performance advantage of a TreeSet. \$\endgroup\$ – Stefan Reich Mar 7 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.