Linear-time Memoization with Java


  • 0
    O
    • If any of pattern or str is empty, return false.
    • Split str into tokens. If the number of tokens is not the same as the length of pattern then they can never match.
    • Iterate through the tokens and the characters of the pattern using a single cursor.
    • If the token has previously been encountered but the pattern character hasn't, then it's a mismatch. Return false.
    • If the pattern character has previously been encountered but didn't correspond to the current token, then it's a mismatch. Return false.
    • Store the character to token mapping and store the token in another dedicated data structure for fast lookup.

    Runtime complexity: O(n). Space complexity O(n).

    public class Solution {
        public boolean wordPattern(String pattern, String str) {
            if (pattern.isEmpty() || str.isEmpty()) return false;
            String[] tokens = str.split("\\s");
            if (tokens.length != pattern.length()) return false;
            Map<Character, String> map = new HashMap<>();
            Set<String> words = new HashSet<String>();
            for (int a = 0; a < pattern.length(); a++) {
                char c = pattern.charAt(a);
                if ((!map.containsKey(c) && words.contains(tokens[a]))
                    || (map.containsKey(c) && !tokens[a].equals(map.get(c)))) return false;
                map.put(pattern.charAt(a), tokens[a]); words.add(tokens[a]);
            }
            return true;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.