890-検索と置換モード
前言
LeetCodeのWeekly Contest 98のタイトル検索と置換モードは、元のタイトルの説明は以下の通りです.
単語リストwordsとパターンpatternがあります.wordsのどの単語がパターンと一致しているか知りたいです.
アルファベットの配列pが存在し、モード内の各アルファベットxをp(x)に置き換えると、必要な単語が得られ、単語はモードと一致する.
(思い出すと、アルファベットの配列はアルファベットからアルファベットへの二重放射です.各アルファベットは別のアルファベットにマッピングされ、同じアルファベットにマッピングされていません.)
wordsで指定したモードに一致する単語のリストを返します.
任意の順序で答えを返すことができます.
例:入力:words=["abc","deq","mee","aqq","dkd","ccc","pattern="abb"出力:["mee","aqq"]解釈:「mee」はパターンに一致し、配列{a->m,b->e,...}が存在するためである.「ccc」はモードと一致しない.{a->c,b->c,...}配列ではありません.aとbは同じアルファベットにマッピングされているからです.
問題を解く構想.
この問題は,単語とパターンのマッピング関係を一つのデータ構造で記述する必要があり,パターンと単語のアルファベットの関係が一対一であるため,Mapを直接用いてこの問題を解決することができる.
インプリメンテーションコード
LeetCodeのWeekly Contest 98のタイトル検索と置換モードは、元のタイトルの説明は以下の通りです.
単語リストwordsとパターンpatternがあります.wordsのどの単語がパターンと一致しているか知りたいです.
アルファベットの配列pが存在し、モード内の各アルファベットxをp(x)に置き換えると、必要な単語が得られ、単語はモードと一致する.
(思い出すと、アルファベットの配列はアルファベットからアルファベットへの二重放射です.各アルファベットは別のアルファベットにマッピングされ、同じアルファベットにマッピングされていません.)
wordsで指定したモードに一致する単語のリストを返します.
任意の順序で答えを返すことができます.
例:入力:words=["abc","deq","mee","aqq","dkd","ccc","pattern="abb"出力:["mee","aqq"]解釈:「mee」はパターンに一致し、配列{a->m,b->e,...}が存在するためである.「ccc」はモードと一致しない.{a->c,b->c,...}配列ではありません.aとbは同じアルファベットにマッピングされているからです.
問題を解く構想.
この問題は,単語とパターンのマッピング関係を一つのデータ構造で記述する必要があり,パターンと単語のアルファベットの関係が一対一であるため,Mapを直接用いてこの問題を解決することができる.
インプリメンテーションコード
/**
*
* @param words
* @param pattern
* @return
*/
public List findAndReplacePattern(String[] words, String pattern) {
List result = new ArrayList<>();
char[] patternChars = pattern.toCharArray();
for (String word : words) {
char[] wordChars = word.toCharArray();
//
boolean match = true;
// Map
Map map = new HashMap<>();
for (int i = 0; i < patternChars.length; i++) {
char p = patternChars[i];
char w = wordChars[i];
if (map.containsKey(p)) {//
char value = map.get(p);
if (value != w) {
match = false;
break;
}
} else {
if(map.containsValue(w)){// ,
match = false;
break;
}else {
map.put(p, w);
}
}
}
if (match) {
result.add(word);
}
}
return result;
}