890-kir3i.md

890. Find and Replace Pattern

Solution

• 시간복잡도: O(WN), W는 단어의 수, N은 단어의 길이

• 알고리즘

  구현, 문자열 처리

• 풀이설명

  주어진 단어가 pattern과 같은 패턴의 단어인지 확인하는 문제입니다. 각 문자열에 대해 주어진 패턴으로 치환될 수 있는지 확인해주면 됩니다. 이 때 각 문자가 어떻게 매칭되는지 나타내기 위해 HashMap을 이용했습니다.

• 소스코드

  • C++

    class Solution {
    public:
        
        vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
            int sz = pattern.size();
            vector<string> ans;
            for(const string &w: words) {
                bool ok = true;
                unordered_map<char, char> trans;
                unordered_set<char> used;
                for(int i=0; i<sz && ok; i++) {
                    if(trans.find(pattern[i]) == trans.end()) {
                        ok &= (used.find(w[i]) == used.end());
                        trans[pattern[i]] = w[i];
                        used.insert(w[i]);
                    }
                    else {
                        ok &= (trans[pattern[i]] == w[i]);
                    }
                }
                if(ok)
                    ans.push_back(w);
            }
            return ans;
        }
    };

  • Python

    class Solution:
        def findAndReplacePattern(self, words, pattern):
            sz = len(pattern)
            ans = []
            for w in words:
                ok = True
                trans = {}
                used = set([])
                for i in range(sz):
                    if pattern[i] not in trans:
                        if w[i] in used:
                            ok = False
                            break
                        trans[pattern[i]] = w[i]
                        used.add(w[i])
                    elif trans[pattern[i]] != w[i]:
                        ok = False
                        break
                if ok:
                   ans.append(w)
            return ans

  • Java

    class Solution {
        public Map<Character, Character> trans = new HashMap<Character, Character>();
        public Set<Character> used = new HashSet<Character>();
        public List<String> findAndReplacePattern(String[] words, String pattern) {
            int sz = pattern.length();
            List<String> ans = new ArrayList<String>();
            for(String w: words) {
                Boolean ok = true;
                trans.clear();
                used.clear();
                for(int i=0; i<sz && ok; i++) {
                    if(!trans.containsKey(pattern.charAt(i))) {
                        ok &= !used.contains(w.charAt(i));
                        trans.put(pattern.charAt(i), w.charAt(i));
                        used.add(w.charAt(i));
                    }
                    else {
                        ok &= (trans.get(pattern.charAt(i)) == w.charAt(i));
                    }
                }
                if(ok)
                    ans.add(w);
            }
            return ans;
        }
    }