tcw165 · August 18, 2019 11:09
diff --git a/dp-solution-for-regular-expression-leetcode.java b/dp-solution-for-regular-expression-leetcode.java
 class Solution {
    
    private final static char NULL_CHAR = '_';
    private final static int PADDING = 1;
    
    public boolean isMatch(String s, String p) {
        final List<String> pattern = extractPattern(p);
        
        // System.out.println(String.format("Search string: %s", s));
        // System.out.println(String.format("Regex pattern: %s", pattern));
        
        // Note: Padding to the string is extremely important for the case such as:
        // s: ""
        // p: ".*"
        final boolean[][] dpMap = new boolean[pattern.size()][s.length() + PADDING];
        traverseBottomUp(s, pattern, dpMap);
        
        // System.out.println(String.format("%s", toPrettyString(dpMap, s, pattern)));
        
        return safeGet(dpMap, pattern.size() - 1, s.length());
    }
    
    /**
     * Represent the graph as a list of expression string.
     * e.g., ["m","i","s*","."]
     */
    private List<String> extractPattern(
        String p
    ) {
        final List<String> graph = new ArrayList<String>();
        
        int end = p.length();
        final int lastIndex = p.length() - 1;
        for (int i = lastIndex; i >= 0; --i) {
            final char c = p.charAt(i);
            if (c >= 'a' && c <= 'z' || c == '.') {
                graph.add(0, p.substring(i, end));
                end = i;
            } else if (c == '*') {
                // No-op
            } else {
                throw new IllegalArgumentException();
            }
        }
        
        return graph;
    }
    
    private void traverseBottomUp(
        String searchStr,
        List<String> pattern,
        boolean[][] dpMap
    ) {
        for (int i = 0; i < pattern.size(); ++i) {
            final String expr = pattern.get(i);
            final char exprChar = expr.charAt(0);
            
            for (int j = 0; j <= searchStr.length(); ++j) {
                final int actualIndex = j - PADDING;
                final boolean notPadding = actualIndex >= 0;
                final char c;
                // First element is the padding to denote null character.
                if (notPadding) {
                    c = searchStr.charAt(actualIndex);
                } else {
                    c = NULL_CHAR;
                }
                
                if (expr.length() == 1) {
                    // Case as alphabet.
                    if (notPadding &&
                        (exprChar == '.' || exprChar == c)) {
                        // Check the remaining string and pattern without this pair.
                        final boolean restWithoutThis = safeGet(dpMap, i - 1, j - 1);
                        
                        dpMap[i][j] = restWithoutThis;
                    } else {
                        // dpMap[i][j] = false; // Not necessary since the field is
                        // initialized as false!
                    }
                } else {
                    // Case as optional alphabet. e.g., "p*" or ".*"
                    
                    // 0 occurance, check the result (solved) without this pattern.
                    final boolean withoutOccur = safeGet(dpMap, i - 1, j);
                    
                    // With occurance.
                    final boolean matched = exprChar == '.' || exprChar == c;
                    final boolean withOccur = matched && safeGet(dpMap, i, j - 1);
                    
                    dpMap[i][j] = withoutOccur || withOccur;
                }
            }
        }
    }
    
    private boolean safeGet(
        boolean[][] dpMap,
        int exprIndex,
        int searchCharIndex
    ) {
        if (exprIndex < 0 && searchCharIndex < 1) {
            return true;
        } else {
            if (exprIndex < 0) {
                // Case as no pattern to match. XD
                return false;
            } else if (searchCharIndex < 0) {
                // Case as Empty char to compare
                return false;
            } else {
                // Both expr index and search index are positive.
                return dpMap[exprIndex][searchCharIndex];
            }
        }
    }
    
    private String toPrettyString(
        boolean[][] dpMap,
        String searchStr,
        List<String> pattern
    ) {
        final StringBuilder sb = new StringBuilder();
        
        // Header
        for (int i = 0; i < pattern.size(); ++i) {
            final String expr = pattern.get(i);
            if (i == 0) {
                sb.append("   ");
            }
            
            sb.append(String.format("%8s", expr));
            
            if (i == pattern.size() - 1) {
                sb.append("\n");
            }
        }
        
        for (int j = 0; j <= searchStr.length(); ++j) {
            final int actualIndex = j - PADDING;
            final char c;
            if (actualIndex >= 0) {
                c = searchStr.charAt(actualIndex);
            } else {
                c = NULL_CHAR;
            }
            
            for (int i = 0; i < pattern.size(); ++i) {
                if (i == 0) {
                    sb.append(String.format("%3s", c));
                }
                
                sb.append(String.format("%8s", dpMap[i][j]));
                
                if (i == pattern.size() - 1) {
                    sb.append("\n");
                }
            }
        }
        
        return sb.toString();
    }
 }
	class Solution {

	private final static char NULL_CHAR = '_';
	private final static int PADDING = 1;

	public boolean isMatch(String s, String p) {
	final List<String> pattern = extractPattern(p);

	// System.out.println(String.format("Search string: %s", s));
	// System.out.println(String.format("Regex pattern: %s", pattern));

	// Note: Padding to the string is extremely important for the case such as:
	// s: ""
	// p: ".*"
	final boolean[][] dpMap = new boolean[pattern.size()][s.length() + PADDING];
	traverseBottomUp(s, pattern, dpMap);

	// System.out.println(String.format("%s", toPrettyString(dpMap, s, pattern)));

	return safeGet(dpMap, pattern.size() - 1, s.length());
	}

	/**
	* Represent the graph as a list of expression string.
	* e.g., ["m","i","s*","."]
	*/
	private List<String> extractPattern(
	String p
	) {
	final List<String> graph = new ArrayList<String>();

	int end = p.length();
	final int lastIndex = p.length() - 1;
	for (int i = lastIndex; i >= 0; --i) {
	final char c = p.charAt(i);
	if (c >= 'a' && c <= 'z' \|\| c == '.') {
	graph.add(0, p.substring(i, end));
	end = i;
	} else if (c == '*') {
	// No-op
	} else {
	throw new IllegalArgumentException();
	}
	}

	return graph;
	}

	private void traverseBottomUp(
	String searchStr,
	List<String> pattern,
	boolean[][] dpMap
	) {
	for (int i = 0; i < pattern.size(); ++i) {
	final String expr = pattern.get(i);
	final char exprChar = expr.charAt(0);

	for (int j = 0; j <= searchStr.length(); ++j) {
	final int actualIndex = j - PADDING;
	final boolean notPadding = actualIndex >= 0;
	final char c;
	// First element is the padding to denote null character.
	if (notPadding) {
	c = searchStr.charAt(actualIndex);
	} else {
	c = NULL_CHAR;
	}

	if (expr.length() == 1) {
	// Case as alphabet.
	if (notPadding &&
	(exprChar == '.' \|\| exprChar == c)) {
	// Check the remaining string and pattern without this pair.
	final boolean restWithoutThis = safeGet(dpMap, i - 1, j - 1);

	dpMap[i][j] = restWithoutThis;
	} else {
	// dpMap[i][j] = false; // Not necessary since the field is
	// initialized as false!
	}
	} else {
	// Case as optional alphabet. e.g., "p" or "."

	// 0 occurance, check the result (solved) without this pattern.
	final boolean withoutOccur = safeGet(dpMap, i - 1, j);

	// With occurance.
	final boolean matched = exprChar == '.' \|\| exprChar == c;
	final boolean withOccur = matched && safeGet(dpMap, i, j - 1);

	dpMap[i][j] = withoutOccur \|\| withOccur;
	}
	}
	}
	}

	private boolean safeGet(
	boolean[][] dpMap,
	int exprIndex,
	int searchCharIndex
	) {
	if (exprIndex < 0 && searchCharIndex < 1) {
	return true;
	} else {
	if (exprIndex < 0) {
	// Case as no pattern to match. XD
	return false;
	} else if (searchCharIndex < 0) {
	// Case as Empty char to compare
	return false;
	} else {
	// Both expr index and search index are positive.
	return dpMap[exprIndex][searchCharIndex];
	}
	}
	}

	private String toPrettyString(
	boolean[][] dpMap,
	String searchStr,
	List<String> pattern
	) {
	final StringBuilder sb = new StringBuilder();

	// Header
	for (int i = 0; i < pattern.size(); ++i) {
	final String expr = pattern.get(i);
	if (i == 0) {
	sb.append(" ");
	}

	sb.append(String.format("%8s", expr));

	if (i == pattern.size() - 1) {
	sb.append("\n");
	}
	}

	for (int j = 0; j <= searchStr.length(); ++j) {
	final int actualIndex = j - PADDING;
	final char c;
	if (actualIndex >= 0) {
	c = searchStr.charAt(actualIndex);
	} else {
	c = NULL_CHAR;
	}

	for (int i = 0; i < pattern.size(); ++i) {
	if (i == 0) {
	sb.append(String.format("%3s", c));
	}

	sb.append(String.format("%8s", dpMap[i][j]));

	if (i == pattern.size() - 1) {
	sb.append("\n");
	}
	}
	}

	return sb.toString();
	}
	}