Java solution, use the similar idea in Isomorphic Strings, "lazy update"

  • -1

    Basically we will only store and compare the first appearance index of key.

    public boolean wordPattern(String pattern, String str) {
        //split the str based on " ", as described by the problem, it will be guaranteed to get word by word
        String[] strs= str.split(" ");
        //if not same length, we will return false
        if(strs.length != pattern.length()) return false;
        //create two HashMap to build one-to-one relationship
        //key is char/string, value is index of FIRST appearance
        HashMap<Character, Integer> map1 = new HashMap<Character, Integer>();
        HashMap<String, Integer> map2 = new HashMap<String, Integer>();
        for(int i = 0; i < pattern.length(); i++){
            char c = pattern.charAt(i);
            //since now we don't have default value in map, we will firstly set the first appearance index.
            // If one of them has already been seen before, then our hashMap will have difference
            //first appearance indexes for this pair.
                map1.put(c, i);
                map2.put(strs[i], i);
            //if FIRST appearance index is not same, we will return false
            //NOTE: we save Integer as value in map, and Integer is object, so we can't use "==" to compare
            //we need !.equals()
            if(!map1.get(c).equals(map2.get(strs[i]))) return false;
        return true;

  • 0

    optimise plz..Instead of using 2 HashMap , try using 2 HashSet.

  • 0

    How about this solution :

       public class Solution {
        public boolean wordPattern(String pattern, String str) {
            if(pattern == null || str == null) return false; 
            HashMap <Character,String> myMap = new HashMap<Character,String>(); 
            HashSet<String> checkExistance = new HashSet<String>(); 
            str = str.trim(); 
            String[] stringArray = str.split(" "); 
            if(stringArray.length != pattern.length()) return false; 
            for(int i=0; i<pattern.length();i++) {
                Character myChar = pattern.charAt(i); 
                if(myMap.containsKey(myChar)) {
                    String temp = myMap.get(myChar);
                    if(!temp.equals(stringArray[i])) return false; 
                } else {
                    if(checkExistance.contains(stringArray[i])) return false; 
            return true; 

Log in to reply

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