Very fast (3ms) Java Solution using HashMap


  • 55
    C
    public class Solution {
        public boolean wordPattern(String pattern, String str) {
            String[] arr= str.split(" ");
            HashMap<Character, String> map = new HashMap<Character, String>();
            if(arr.length!= pattern.length())
                return false;
            for(int i=0; i<arr.length; i++){
                char c = pattern.charAt(i);
                if(map.containsKey(c)){
                    if(!map.get(c).equals(arr[i]))
                        return false;
                }else{
                    if(map.containsValue(arr[i]))
                        return false;
                    map.put(c, arr[i]);
                }    
            }
            return true;
        }
    }

  • 1
    X

    Normal, but clean and efficient.


  • 8
    A

    I am little struggling with the efficiency at here.
    It seems the time complexity of running "map.containsValue(arr[i])" is O(n).


  • 0
    C

    You are right about the O(n) compelxity.


  • 0
    V

    Totally the same solution with mine


  • 5
    J

    To avoid map.containsValue(arr[i]), you can add an extra map to save <String, Character>, my code as below:

    public class Solution {
    public boolean wordPattern(String pattern, String str) {

        String[] strs = str.split(" ");
        
        if(pattern.length() != strs.length) return false;
        
        HashMap<Character, String> hm1 = new HashMap<Character, String>();
        HashMap<String, Character> hm2 = new HashMap<String, Character>();
        for(int i=0; i<pattern.length(); ++i) {
            if(hm1.containsKey(pattern.charAt(i))) {
                if(!hm1.get(pattern.charAt(i)).equals(strs[i])) return false;
            }
            else {
                if(hm2.containsKey(strs[i])) return false;
                else {
                    hm1.put(pattern.charAt(i), strs[i]);
                    hm2.put(strs[i], pattern.charAt(i));
                }
            }
        }
        
        return true;
    }
    

    }


  • 0
    J

    Thanks,different from mine!


  • 3
    N

    @jamesye maybe use Set instead of second Map is sufficient enough. If the Set contains the word, it has been visited and it's corresponding Character has to be in the first map if the pattern matches.


  • 0

    @airwindow so the worst time complexity is O(n^2) right?


  • 0
    M

    @processvs.thread
    Yes.
    Use map.containsValue() makes it O(n^2)


  • 0

    @chasethebug said in Very fast (3ms) Java Solution using HashMap:

    Very straightforward solution! I modified your code a little bit to avoid nested if statements.

    public boolean wordPattern(String pattern, String str) {
            String[] words = str.split(" ");
            if (words.length != pattern.length()) return false;
            Map<Character, String> map = new HashMap<>();
            for (int i = 0; i < pattern.length(); i++) {
                char key = pattern.charAt(i);
                String word = words[i];
                if (map.containsKey(key) && !map.get(key).equals(word)) return false;
                if (!map.containsKey(key) && map.containsValue(word)) return false;
                map.put(key, word);
            }
            return true;
        }
    

Log in to reply
 

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