Skip to content

890. Find and Replace Pattern 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
    vector<string> ans;

    for (const string& word : words)
      if (isIsomorphic(word, pattern))
        ans.push_back(word);

    return ans;
  }

 private:
  bool isIsomorphic(const string& w, const string& p) {
    vector<int> map_w(128);
    vector<int> map_p(128);

    for (int i = 0; i < w.length(); ++i) {
      if (map_w[w[i]] != map_p[p[i]])
        return false;
      map_w[w[i]] = i + 1;
      map_p[p[i]] = i + 1;
    }

    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public List<String> findAndReplacePattern(String[] words, String pattern) {
    List<String> ans = new ArrayList<>();

    for (final String word : words)
      if (isIsomorphic(word, pattern))
        ans.add(word);

    return ans;
  }

  private boolean isIsomorphic(final String w, final String p) {
    Map<Character, Integer> map_w = new HashMap<>();
    Map<Character, Integer> map_p = new HashMap<>();

    for (Integer i = 0; i < w.length(); ++i)
      if (map_w.put(w.charAt(i), i) != map_p.put(p.charAt(i), i))
        return false;

    return true;
  }
}

1
2
3
4
5
class Solution:
  def findAndReplacePattern(self, words: list[str], pattern: str) -> list[str]:
    def isIsomorphic(w: str, p: str) -> bool:
      return [*map(w.index, w)] == [*map(p.index, p)]
    return [word for word in words if isIsomorphic(word, pattern)]