Leetcode - 290. Word Pattern

문제

isomorphic 패턴 문자열과 문자열집합이 isomolphic한지 체크하는 문제. 비슷한 문제로는 다음의 문제가 있고. 여기서는 'a' -> "dog" 문자가 문자열과 매핑되어야하는점이 다르다.

https://leetcode.com/problems/word-pattern/

Input: pattern = "abba", s = "dog cat cat dog"
Output: true

유사문제

• Leetcode - 205. Isomorphic Strings
• Leetcode - 890. Find and Replace Pattern

해결 O(N)

'a' -> "dog" 로 매핑하기 위해서는 이전 문제처럼 table[26]에 매핑하면 된다. 그런데 "dog" -> 'a' 처럼 반대로 매핑하는 경우는 hash 테이블에 저장해야한다. (collision을 위해 링크드리스트 기반이어야함)

시간복잡도는 O(N)이지만 더 빠른 방법이 있긴한듯.

#define HSIZE  1093
struct elem {
    char *s;
    char pat;
    struct elem *next;
};
struct elem *hashtable[HSIZE];

int hash(char *s)
{
    unsigned long int hval = 0;
    
    while (*s != '\0')
        hval = hval * 31 + *s++;
    return hval % HSIZE;
}

enum {
    SEARCH = 0,
    CREATE
};
struct elem *hash_search_insert(char *s, char pat, int create)
{
    int hval = hash(s);
    struct elem *node = hashtable[hval];
    for (;node != NULL; node = node->next) {
        if (strcmp(node->s, s) == 0)
            return node;
    }
    if (create) {
        node = malloc(sizeof(struct elem));
        node->s = malloc(sizeof(char) * strlen(s) + 1);
        strcpy(node->s, s);
        node->pat = pat; 
        node->next = hashtable[hval];
        hashtable[hval] = node;
    }
    return node;
}

bool wordPattern(char * pattern, char * s){
    int psize = strlen(pattern);
    int tkncnt = 0;
    int wlenth = 0;
    int cidx = 0;
    int pcnt = 0;
    char **ctable = (char **)calloc(26, sizeof(char *));
    memset(hashtable, NULL, sizeof(struct elem *) * HSIZE);
    
    char *token = strtok(s, " ");
	while (token != NULL) {
        /* 1. mapping: pattern[i] -> str[i] */
        cidx = pattern[pcnt] - 'a';
        wlenth = strlen(token) + 1;
        if (ctable[cidx] != NULL && strcmp(ctable[cidx], token))
            return false;
        ctable[cidx] = (char *)calloc(wlenth, sizeof(char));
        strcpy(ctable[cidx], token);
        
        /* 2. mapping: str[i] -> pattern[i] */
        struct elem *n = hash_search_insert(token, pattern[pcnt], SEARCH);
        if (n && n->pat != pattern[pcnt]) // hashtable["cat"] must be 'b'
            return false;
        hash_search_insert(token, pattern[pcnt], CREATE);
        
        pcnt++;
        tkncnt++;
		token = strtok(NULL, " ");
	}
    
    if (psize != tkncnt)
        return false;
        
    return true; 
}