Leetcode - 890. Find and Replace Pattern

문제

주어진 문자열 집합에서 패턴과 isomorphic한 문자열만 리턴하라. 문제를 이해하기 위해 이 문제의 쉬운버전인 Leetcode-205.-Isomorphic-Strings 문제를 사전에 참고.

Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]

https://leetcode.com/problems/find-and-replace-pattern/

해결 O(N)

아래 is_ismorphic() 함수에 대한 자세한 설명은 링크 참조 -> Leetcode-205.-Isomorphic-Strings
링크의 함수와 다른점은 이 문제는 소문자만 사용했기 때문에 map의 크기를 26으로 해도된다. 하지만 여기서 27로 했는데, map[i] 가 0이 되면 조건처리를 정상적으로 하지 못하기 때문이다. 따라서 +1을 더해줫고 크기가 27이 되었다. 문자를 map에 저장하기 위해 간단한 hash()함수로 변환.

결과는 0ms 100% 가 나왔음.

Runtime: 0 ms, faster than 100.00% of C online submissions for Find and Replace Pattern.
Memory Usage: 6.1 MB, less than 100.00% of C online submissions for Find and Replace Pattern.

int hash(int val)
{
    // a - 'a' will be 0, make it to 1
    return val - 'a' + 1;
}

bool is_ismorphic(char *p, char *s)
{
    int map_p[27] = {0};
    int map_s[27] = {0};
    int ssize = strlen(p);
    
    for (int i = 0; i < ssize; i++) {
        if (map_p[hash(p[i])] && (map_p[hash(p[i])] != hash(s[i])))
            return false;
        if (map_s[hash(s[i])] && (map_s[hash(s[i])] != hash(p[i])))
            return false;
        map_p[hash(p[i])] = hash(s[i]);
        map_s[hash(s[i])] = hash(p[i]);
    } 
    return true;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char ** findAndReplacePattern(char ** words, int wordsSize, char * pattern, int* returnSize){
    char **ret = (char **)calloc(wordsSize, sizeof(char*));
    int retcnt = 0;
    int ssize = strlen(pattern);
    for (int i = 0; i < wordsSize; i++) {
        if (is_ismorphic(pattern, words[i])) {
            ret[retcnt] = (char *)calloc(ssize + 1, sizeof(char));
            strcpy(ret[retcnt], words[i]);
            retcnt++;
        }
    }
    *returnSize = retcnt;
    return ret;
}

아래는 c++ stl의 vector와 unordered_map으로 푼것. 알고리즘은 동일.

class Solution {
    bool check_isomorphic(string str, string pat) {
        int ssize = str.length();
        unordered_map<char, char> table_str;
        unordered_map<char, char> table_pat;
        for (int i = 0; i < ssize; i++) {
            if (table_str[str[i]] && table_str[str[i]] != pat[i])
                return false;
            table_str[str[i]] = pat[i];
            if (table_pat[pat[i]] && table_pat[pat[i]] != str[i])
                return false;
            table_pat[pat[i]] = str[i];
        }
        return true;
    }
public:
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        vector<string> ret;
        
        for (auto s: words) {
            if (check_isomorphic(s, pattern))
                ret.push_back(s);
        }
        return ret;
    }
};