Easy Java Solution without using split()


  • 1
    K

    I noticed a lot of the solutions use split(" "), which would copy all of the words into an array. This is an unnecessary use of space and time. Here you can do it without using split.

    public boolean wordPattern(String pattern, String str) {
        Map<Character, String> char2word = new HashMap<>();
        int begWord = 0;
        int patIndex = 0;
        while (patIndex < pattern.length() && begWord < str.length()) {
            char curChar = pattern.charAt(patIndex);
            int endWord = begWord;
            
            // go through the word and make sure it matches the one in the map
            // (if there is one in the map for this curChar)
            while (endWord < str.length() && str.charAt(endWord) != ' ') {
                if (char2word.containsKey(curChar) && char2word.get(curChar).charAt(endWord - begWord) != str.charAt(endWord)) {
                    return false;
                }
                endWord++;
            }
            // if this word has been mapped to a letter other than curChar
            if (!char2word.containsKey(curChar) && char2word.containsValue(str.substring(begWord, endWord))) {
                return false;
            }
            
            char2word.put(curChar, str.substring(begWord, endWord));
            begWord = endWord + 1;
            patIndex++;
        }
        // make sure we've used all of pattern and str
        if (patIndex < pattern.length() || begWord < str.length()) {
            return false;
        }
        return true;
    }

  • 0
    B
    /**
     * 99.35% on 2016-01-19
     * No split() or Map used
     * @author badsheep
     * @param pattern
     * @param str
     * @return
     */
    public boolean wordPattern(String pattern, String str) {
    	
    	char[] patternArr = pattern.toCharArray();
    	char[] strArr = str.toCharArray();
    	
    	if(patternArr.length==0 && strArr.length==0){
    		return true;
    	}else if(patternArr.length!=0 && strArr.length!=0){
    		char[][] mapArr = new char[26][];
    		
    		int offset = 0;
    		int patternArrIndex = 0;
    		
    		char[] strPartTmp = null;
    		char[] strMapTmp = null;
    		
    		while(patternArrIndex < patternArr.length){
    			int from = patternArrIndex + offset;
    			if(from > strArr.length){
    				return false;
    			}
    			while((patternArrIndex + offset)<strArr.length && strArr[patternArrIndex + offset] != ' '){
    				offset++;
    			}
    			int to = patternArrIndex + offset;
    			strPartTmp = Arrays.copyOfRange(strArr, from, to);
    			strMapTmp = mapArr[patternArr[patternArrIndex]-97];
    			if(strMapTmp == null){
    				boolean ignore = false;
    				int m=0;
    				while(m<mapArr.length){
    					m++;
    					if(mapArr[m-1] == null) continue;
    					if(Arrays.equals(mapArr[m-1], strPartTmp)){
    						ignore = true;
    						break;
    					}
    				}
    				if(!ignore){
    					mapArr[patternArr[patternArrIndex]-97] = strPartTmp;
    				}else{
    					if((m - 1 + 97) != patternArr[patternArrIndex]){
    						return false;
    					}
    				}
    			}else{
    				if(!Arrays.equals(strMapTmp, strPartTmp)){
    					return false;
    				}
    			}
    			patternArrIndex++;
    		}
    		if(patternArrIndex + offset<strArr.length){
    			return false;
    		}
    		return true;
    	}else{
    		return false;
    	}
    }

Log in to reply
 

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