290. Word Pattern (Easy)

https://leetcode.com/problems/word-pattern/

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Example 1:

Input: pattern = "abba", str = "dog cat cat dog"
Output: true

Example 2:

Input:pattern = "abba", str = "dog cat cat fish"
Output: false

Example 3:

Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false

Example 4:

Input: pattern = "abba", str = "dog dog dog dog"
Output: false

Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.

Solutions

class Solution {

    public boolean wordPattern(String pattern, String str) {
        int size1 = pattern.length();

        String[] splits = str.split(" ");
        int size2 = splits.length;

        if (size1 != size2) {
            return false;
        }

        Map<Character, List<Integer>> map1 = new HashMap<>();
        Map<String, List<Integer>> map2 = new HashMap<>();

        for (int i = 0; i < size1; i++) {
            char c = pattern.charAt(i);
            if (!map1.containsKey(c)) {
                map1.put(c, new ArrayList<>());
            }

            map1.get(c).add(i);
        }

        for (int i = 0; i < size2; i++) {
            String s = splits[i];
            if (!map2.containsKey(s)) {
                map2.put(s, new ArrayList<>());
            }

            map2.get(s).add(i);
        }

        Set<Character> visited = new HashSet<>();
        boolean ans = true;

        for (int i = 0; i < size1; i++) {
            char c = pattern.charAt(i);
            String s = splits[i];

            if (visited.contains(c)) {
                continue;
            }

            String idx1 = map1.get(c).toString();
            String idx2 = map2.get(s).toString();

            if (!idx1.equals(idx2)) {
                ans = false;
                break;
            }

            visited.add(c);
        }

        return ans;
    }
}

Incorrect Solutions

References