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


  • -1
    H

    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.
            if(!map1.containsKey(c)){
                map1.put(c, i);
            }
            
            if(!map2.containsKey(strs[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
    A

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


  • 0
    N

    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; 
                    myMap.put(myChar,stringArray[i]);
                    checkExistance.add(stringArray[i]);
                }
                
            }
            return true; 
        }
    }

Log in to reply
 

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