Word Pattern

Given apatternand a stringstr, find ifstrfollows the same pattern.

Here follow means a full match, such that there is a bijection between a letter inpatternand a non-empty word instr.

Examples:

1. pattern ="abba", str ="dog cat cat dog"

   should return true.

2. pattern ="abba", str ="dog cat cat fish"

   should return false.

3. pattern ="aaaa", str ="dog cat cat dog"

   should return false.

4. pattern ="abba", str ="dog dog dog dog"

   should return false.

Notes: You may assumepatterncontains only lowercase letters, andstrcontains lowercase letters separated by a single space.

class Solution(object):
    def wordPattern(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        if not pattern and not str:
            return True

        # since str has words separated by spaces    
        str_arr = str.split()
        if len(str_arr) != len(pattern):
            return False

        dict = {}
        start = 0
        for idx in xrange(len(pattern)):
            ch = pattern[idx]
            substr = ''
            #/////////////////////////////////////////
            # easy to obtain substr when the str has ' ' (space) separating words
            #/////////////////////////////////////////
            for idx2 in xrange(start, len(str)):
                if str[idx2] != ' ':
                    substr += str[idx2]
                else:
                    start = idx2 + 1
                    break;

            #print 'ch: ', ch, ' substr: ', substr, ' start: ', start
            if ch not in dict:
                if substr not in dict.values():
                    #print 'hashing: ', ch, ' -> ', substr
                    dict[ch] = substr
                else:
                    return False

            else:
                if dict[ch] != substr:
                    return False

        return True