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\$
4
  • \$\begingroup\$ Welcome to Code Review! Good job on your first question. \$\endgroup\$ Commented Oct 31, 2015 at 0:25
  • \$\begingroup\$ One interesting test set from Tom Anderson's comment: "pot" and "potash" in set; query "potato". \$\endgroup\$ Commented Mar 8, 2019 at 7:45
  • \$\begingroup\$ Java 7 without any extra libs does this rule out open coding / roll-your-own? \$\endgroup\$ Commented Mar 8, 2019 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\$ Commented Mar 8, 2019 at 7:55

3 Answers 3

Reset to default
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\$
6
  • \$\begingroup\$ But my prefix match is on the values not on the keys \$\endgroup\$ Commented Oct 7, 2015 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\$ Commented Oct 7, 2015 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\$ Commented Oct 7, 2015 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\$ Commented Mar 14, 2018 at 17:04
  • 1
    \$\begingroup\$ This one doesn't work. \$\endgroup\$ Commented Mar 7, 2019 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\$
7
  • \$\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\$ Commented Oct 6, 2015 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\$ Commented Oct 6, 2015 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\$ Commented Oct 6, 2015 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\$ Commented Oct 6, 2015 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\$ Commented Oct 7, 2015 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\$
1
  • \$\begingroup\$ I think this works, but it almost negates the whole performance advantage of a TreeSet. \$\endgroup\$ Commented Mar 7, 2019 at 22:46

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.