Java solution based on Word Pattern I

  • 3

    This method is based on the solution of Word Pattern I
    Here is the solution of Word Pattern I, one to one mapping check each character of pattern with each item of string

    public boolean wordPattern(String pattern, String str) {
            String[] array = str.split(" ");
            if(pattern.length() != array.length) return false;
            Map map = new HashMap();
            for(Integer i = 0; i < array.length; ++i) {
                if(map.put(pattern.charAt(i), i) != map.put(array[i], i)) return false;
            return true;

    Based on the first solution, we can use the same way to check if it is a valid result. Remember to set the mapping value back when current case is not working.

    public boolean wordPatternMatch(String pattern, String str) {
            if(pattern.length()==0 && str.length()==0) return true;
            if(pattern.length()==0) return false;
            HashMap map = new HashMap();
            return helper(pattern, str, 0, 0, map);
        public boolean helper(String pattern, String str, Integer i, int j, HashMap map) {
            if(i==pattern.length() && j==str.length()) return true;
            if(i>=pattern.length() || j>=str.length()) return false;
            for(int k = j+1; k <= str.length(); ++k) {
                String temp = str.substring(j, k);
                char c = pattern.charAt(i);
                Object a = map.put(c, i);
                Object b = map.put(temp, i);
                if(a == b) {
                    if(helper(pattern, str, i+1, k, map)) return true;
                map.put(c, a);
                map.put(temp, b);
            return false;

  • 0

    I like it, short and clean to write!

Log in to reply

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