# Three ways to solve this problem in Java

• Before solving this problem, we need to know which operation is called the most.

If f is more frequently than WordFilter, use method 1.
If space complexity is concerned, use method 2.
If the input string array might change frequently, use method 3.

< Method 1 >
WordFilter: Time = O(NL^2)
f: Time = O(1)
Space = O(NL^2)
Note: N is the size of input array and L is the max length of input strings.

``````class WordFilter {
HashMap<String, Integer> map = new HashMap<>();

public WordFilter(String[] words) {
for(int w = 0; w < words.length; w++){
for(int i = 0; i <= 10 && i <= words[w].length(); i++){
for(int j = 0; j <= 10 && j <= words[w].length(); j++){
map.put(words[w].substring(0, i) + "#" + words[w].substring(words[w].length()-j), w);
}
}
}
}

public int f(String prefix, String suffix) {
return (map.containsKey(prefix + "#" + suffix))? map.get(prefix + "#" + suffix) : -1;
}
}

``````

< Method 2 >
WordFilter: Time = O(NL)
f: Time = O(N)
Space = O(NL)

``````class WordFilter {
HashMap<String, List<Integer>> mapPrefix = new HashMap<>();
HashMap<String, List<Integer>> mapSuffix = new HashMap<>();

public WordFilter(String[] words) {

for(int w = 0; w < words.length; w++){
for(int i = 0; i <= 10 && i <= words[w].length(); i++){
String s = words[w].substring(0, i);
if(!mapPrefix.containsKey(s)) mapPrefix.put(s, new ArrayList<>());
}
for(int i = 0; i <= 10 && i <= words[w].length(); i++){
String s = words[w].substring(words[w].length() - i);
if(!mapSuffix.containsKey(s)) mapSuffix.put(s, new ArrayList<>());
}
}

public int f(String prefix, String suffix) {

if(!mapPrefix.containsKey(prefix) || !mapSuffix.containsKey(suffix)) return -1;
List<Integer> p = mapPrefix.get(prefix);
List<Integer> s = mapSuffix.get(suffix);
int i = p.size()-1, j = s.size()-1;
while(i >= 0 && j >= 0){
if(p.get(i) < s.get(j)) j--;
else if(p.get(i) > s.get(j)) i--;
else return p.get(i);
}
return -1;
``````

< Method 3 >
WordFilter: Time = O(1)
f: Time = O(NL)
Space = O(1)

``````class WordFilter {
String[] input;
public WordFilter(String[] words) {
input = words;
}
public int f(String prefix, String suffix) {
for(int i = input.length-1; i >= 0; i--){
if(input[i].startsWith(prefix) && input[i].endsWith(suffix)) return i;
}
return -1;
}
}

``````

• @moto72 For some `N` in your complexity analysis, did you actually mean `L`, i.e., the max length of each word?

• @zzg_zzm Yes. You're right.
Some of them should be the max length of each word, as updated.

• This post is deleted!

• Do we consider hash(String) O(1) or O(L) in Java?

Java hashCode()

• Hi, regarding your second method, you say WordFilter is O(NL), however it's O(NL^2) because you have 2 loops (with sizes N and L) and in the innermost loop you use `String s = words[w].substring(0, i)` which in turn works in O(L), so overall complexity is O(NL^2).

Also regarding first method, as someone already mentioned, getting hash of the string is linear to the length of the string, so `map.put(words[w].substring(0, i) + "#" + words[w].substring(words[w].length()-j), w);` also takes O(L) time for calculating hash. Therefore time complexity for WordFilter in first method is O(NL^3)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.