1 ms fastest JAVA solution


  • 0
    Q

    When I first submit my back-trace solution, it takes 58 ms to finish the test case. Then I came across a idea to calculate the length remaining before trying all the possible combinations from this article
    https://discuss.leetcode.com/topic/36076/java-hashset-backtracking-2ms-beats-100
    I added 4 lines in the code and it got improved to 1 ms.

    public class Solution {
        public boolean wordPatternMatch(String pattern, String str) {
            char[] pChar = pattern.toCharArray();
            char[] sChar = str.toCharArray();
            return isMatch(pChar, 0, sChar, 0, new String[26], new HashSet<String>());
        }
        public boolean isMatch(char[] pChar, int pStart, char[] sChar, int sStart, String[] pMap, HashSet<String> visitSet) {
            if (pStart > pChar.length-1 && sStart > sChar.length-1) {
                return true;
            } else if (pStart > pChar.length-1 || sStart > sChar.length-1) {
                return false;
            }
            
            if (pMap[pChar[pStart]-'a'] == null) {            
                // -----------------------------I added these 4 lines--------------------------
                int endPoint = sChar.length-1;
        	    for(int i=pChar.length-1; i>pStart; i--) {
        	        endPoint -= pMap[pChar[i]-'a']==null ? 1 : pMap[pChar[i]-'a'].length();
        	    }
                //----------------------------------------------------------------------------------- 
                for (int i = sStart; i <= endPoint; ++i) {
                    String ts = new String(sChar, sStart, i-sStart+1);
                    if (visitSet.contains(ts)) {
                        continue;
                    }
                    pMap[pChar[pStart]-'a'] = ts;
                    visitSet.add(ts);
                    if (isMatch(pChar, pStart+1, sChar, i+1, pMap, visitSet)) {
                        return true;
                    }
                    pMap[pChar[pStart]-'a'] = null;
                    visitSet.remove(ts);
                }
            } else {
                String vString = pMap[pChar[pStart]-'a'];
                if (sStart+vString.length() > sChar.length) {
                    return false;
                }
                String ts = new String(sChar, sStart, vString.length());
                if (vString.equals(ts)) {
                    return isMatch(pChar, pStart+1, sChar, sStart+vString.length(), pMap, visitSet);
                } else {
                    return false;
                }
            }
            
            return false;
        }
    }

Log in to reply
 

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