Образец слова

Проблема дня 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;
    }
}

Спасибо всем!!!