Проблема дня Leetcode [ 01 января 2023 ]
Учитывая pattern
и строку s
, найдите, соответствует ли s
тому же шаблону.
Здесь follow означает полное совпадение, т. е. биекцию между буквой в pattern
и непустым словом в s
.
Пример 1:
Input: pattern = "abba", s = "dog cat cat dog" Output: true
Пример 2:
Input: pattern = "abba", s = "dog cat cat fish" Output: false
Пример 3:
Input: pattern = "aaaa", s = "dog cat cat dog" Output: false
Решение
Как мы знаем, что
«абба» -> «собака кошка кошка собака»
'собака"
‘б’ -> «кошка»
если мы встретим карту с другой строкой, мы можем сказать, что это недопустимый тестовый пример.
«абфа» -> «собака, кошка, собака, собака»
'собака"
‘б’ -> «кошка»
‘ф’ -> «собака»
но собака уже закреплена за a. Итак, мы используем две карты: одна будет отображать собаку -›, а другая — собаку -› a, чтобы мы знали, что собака уже сопоставлена с другим персонажем.
Приступим к коду
class Solution { public boolean wordPattern(String pattern, String s) { String[] tokens = s.split(" "); if(pattern.length() != tokens.length) return false; HashMap<String, Character> map = new HashMap<>(); HashMap<Character, String> reverseMap = new HashMap<>(); for(int i=0;i<tokens.length;i++) { String find = tokens[i]; char pt = pattern.charAt(i); if(!map.containsKey(find)) map.put(find, pt); if(!reverseMap.containsKey(pt)) reverseMap.put(pt, find); char mapPt = map.get(find); String mapStr = reverseMap.get(pt); if(mapPt != pt) return false; if(!mapStr.equals(find)) return false; } return true; } }
Спасибо всем!!!