Word Pattern

Word Pattern I, 这里建了一个map，用到了containsValue()这个方法，这个操作的时间复杂度是O(n)的。这题可以用两个map去优化，避免了有O(n)的操作

public class Solution {
    public boolean wordPattern(String pattern, String str) {
        String[] words = str.split(" ");
        if (pattern.length() != words.length) {
            return false;
        }

        Map<Character, String> map = new HashMap<Character, String>();
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            String word = words[i];

            if (map.containsKey(c)) {
                if (!word.equals(map.get(c))) {
                    return false;
                }
            } else {
                if (map.containsValue(word)) {
                    return false;
                }
                map.put(c, word);
            }
        }

        return true;
    }
}

Isomorphic Strings 解一：跟上一题一样，用了一个map，速度是击败30%

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        Map<Character, Character> map = new HashMap<Character, Character>();
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);

            if (map.containsKey(c1)) {
                if (map.get(c1) != c2) {
                    return false;
                }
            } else {
                if (map.containsValue(c2)) {
                    return false;
                }
                map.put(c1, c2);
            }
        }

        return true;
    }
}

解二: 用了两个map，避免有出现O(n)的操作，但是速度反而慢了，击败20%

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        Map<Character, Character> map1 = new HashMap<Character, Character>();
        Map<Character, Character> map2 = new HashMap<Character, Character>();
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);

            if (map1.containsKey(c1) && map2.containsKey(c2)) {
                if (map1.get(c1) != c2 || map2.get(c2) != c1) {
                    return false;
                }
            } else if (map1.containsKey(c1) || map2.containsKey(c2)) {
                return false;
            } else {
                map1.put(c1, c2);
                map2.put(c2, c1);
            }
        }

        return true;
    }
}

Word Pattern II

public class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        boolean[] result = new boolean[1];
        Map<Character, String> map = new HashMap<Character, String>();
        dfs(result, pattern, str, 0, 0, map);
        return result[0];
    }

    private void dfs(boolean[] result, String pattern, String str, int i, int j, Map<Character, String> map) {
        if (result[0]) {
            return;
        } else if (i == pattern.length() && j == str.length()) {
            result[0] = true;
            return;
        } else if (i == pattern.length() || j == str.length()) {
            return;
        }

        char c = pattern.charAt(i);
        if (map.containsKey(c)) {
            String word = map.get(c);
            if (j + word.length() > str.length()) {
                return;
            }
            String word2 = str.substring(j, j + word.length());
            if (!word.equals(word2)) {
                return;
            } else {
                dfs(result, pattern, str, i + 1, j + word.length(), map);
            }
        } else {
            for (int index = j; index < str.length(); index++) {
                String word = str.substring(j, index + 1);
                if (map.containsValue(word)) {
                    continue;
                }
                map.put(c, word);
                dfs(result, pattern, str, i + 1, j + word.length(), map);
                map.remove(c);
            }
        }
    }
}