You have a list of\u00a0 A word matches the pattern if there exists a permutation of letters\u00a0 (Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.<\/em>)<\/p>\n Return a list of the words in\u00a0 You may return the answer in any order.<\/p>\n Example 1:<\/strong><\/p>\n Note:<\/strong><\/p>\n <\/ins><\/p>\n Time complexity: O(n*l)<\/p>\n Space complexity: O(128) -> O(26)<\/p>\n C++<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" Problem You have a list of\u00a0words\u00a0and a\u00a0pattern, and you want to know which words in\u00a0words\u00a0matches the pattern. A word matches the pattern if there exists…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[47],"tags":[177,315,4],"class_list":["post-3637","post","type-post","status-publish","format-standard","hentry","category-string","tag-medium","tag-permuation","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3637","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3637"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3637\/revisions"}],"predecessor-version":[{"id":3639,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3637\/revisions\/3639"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3637"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3637"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3637"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}words<\/code>\u00a0and a\u00a0pattern<\/code>, and you want to know which words in\u00a0words<\/code>\u00a0matches the pattern.<\/p>\np<\/code>\u00a0so that after replacing every letter\u00a0x<\/code>\u00a0in the pattern with\u00a0p(x)<\/code>, we get the desired word.<\/p>\nwords<\/code>\u00a0that match the given pattern.<\/p>\nInput: <\/strong>words = [\"abc\",\"deq\",\"mee\",\"aqq\",\"dkd\",\"ccc\"]<\/span>, pattern = \"abb\"<\/span>\r\nOutput: <\/strong>[\"mee\",\"aqq\"]<\/span>\r\nExplanation: <\/strong>\"mee\" matches the pattern because there is a permutation {a -> m, b -> e, ...}. \r\n\"ccc\" does not match the pattern because {a -> c, b -> c, ...} is not a permutation,\r\nsince a and b map to the same letter.<\/pre>\n\n
1 <= words.length <= 50<\/code><\/li>\n1 <= pattern.length = words[i].length\u00a0<= 20<\/code><\/li>\n<\/ul>\nSolution: Remember\u00a0the last pos of each char.<\/h1>\n
\/\/ Author: Huahua\r\n\/\/ Running time: 0 ms\r\nclass Solution {\r\npublic:\r\n vector<string> findAndReplacePattern(vector<string>& words, string pattern) { \r\n vector<string> ans;\r\n for (const string& w : words)\r\n if (match(w, pattern)) ans.push_back(w);\r\n return ans;\r\n }\r\nprivate:\r\n bool match(const string& w, const string& p) {\r\n vector<int> last_pos_w(128, INT_MIN); \/\/ last pos of x in w\r\n vector<int> last_pos_p(128, INT_MIN); \/\/ last pos of x in p\r\n for (int i = 0; i < w.size(); ++i)\r\n if (last_pos_w[w[i]] != last_pos_p[p[i]]) {\r\n return false;\r\n } else {\r\n last_pos_w[w[i]] = last_pos_p[p[i]] = i;\r\n }\r\n return true;\r\n }\r\n};<\/pre>\n