题目

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Example 1:

Input: pattern = "abba", str = "dog cat cat dog"
Output: true
Example 2:

Input:pattern = "abba", str = "dog cat cat fish"
Output: false
Example 3:

Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false
Example 4:

Input: pattern = "abba", str = "dog dog dog dog"
Output: false

Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

解析

读完本题基本的思路已经有了。先将str按空格进行split，然后再依次和pattern进行类比。在这里要注意的是，假如pattern b所对应的value为dog，若dog在pattern b之前的对应中已经出现，该种情况为false。这种情况所对应的input和output示例为：

Input:pattern = "abba", str="dog dog dog dog"
output:false

那么此题的难度便转化为split的实现。
C Standard Library中的string.h没有包含split的函数实现，但是提供了strtok的函数，

char * strtok ( char * str, const char * delimiters );

Split string into tokens
A sequence of calls to this function split str into tokens, which are sequences of contiguous characters separated by any of the characters that are part of delimiters.
On a first call, the function expects a C string as argument for str, whose first character is used as the starting location to scan for tokens. In subsequent calls, the function expects a null pointer and uses the position right after the end of the last token as the new starting location for scanning.

该函数主要根据delimiter将str分隔开来，从第二次调用开始str传NULL，这是因为strtok记住了上次分隔的位置。
因此，可以使用该函数进行split的实现。

代码（C语言）

/*
 * 290. Word Pattern
 * URL: https://leetcode.com/problems/word-pattern/
 */
void split(char* src, const char* separator, char** dest, int* num);
bool wordPattern(char* pattern, char* str) {
    if (str == NULL || pattern == NULL)
        return false;
    
    int patternLen = (int)strlen(pattern);
    
    if (patternLen == 0)
        return false;
    
    // space is separator
    char* separator = " ";
    char* dest[255] = {0};
    int strSplitCount = 0;
    
    const int strLen = (int)strlen(str);
    char* strCopy = (char*)calloc(strLen, sizeof(char));
    
    memcpy(strCopy, str, sizeof(char) * strLen);
    
    split(strCopy, separator, dest, &strSplitCount);
    
    if (strSplitCount == 0 ||
        (patternLen != strSplitCount))
        return false;
    
    // Three are 26 charaters
    char** patternDictArr = (char**)calloc(26, sizeof(char*));
    
    for (int i = 0; i < patternLen; ++i) {
        char curPattern = pattern[i];
        char* curPatternArr = patternDictArr[curPattern - 'a'];
        
        if (!curPatternArr) {
            // if previous dict value is equal to dest[i], it would be false
            for (int j = 0; j < 26; ++j) {
                if (patternDictArr[j] &&
                    strcmp(patternDictArr[j], dest[i]) == 0)  {
                    return false;
                }
            }
            
            patternDictArr[curPattern - 'a'] = dest[i];
        } else {
            if (strcmp(curPatternArr, dest[i]) != 0)
                return false;
        }
    }
    
    return true;
}

void split(char* src, const char* separator, char** dest, int* num) {
    if ((src == NULL || strlen(src) == 0) ||
        (separator == NULL || strlen(separator) == 0))
        return ;
    
    int count = 0;
    char* pNext = strtok(src, separator);
    
    while (pNext) {
        *dest++ = pNext;        // (*dest) = pNext; ++dest;
        
        ++count;
        pNext = strtok(NULL, separator);
    }
    
    *num = count;
}