Java DP solution with O(n) space with detailed explaination
This is a DP O(n) space solution optimized from DP O(mn) space solution\n\nThe optimization is based on Zero-One backpack algorithm and Complete backpack algori
This is a DP O(n) space solution optimized from DP O(mn) space solution\n\nThe optimization is based on Zero-One backpack algorithm and Complete backpack algorithm.\nSo after the optimization, this problem looks more like a mixed backpack problem.\n\n```\n    public boolean isMatch(String s, String p) {\n        boolean[] dp = new boolean[s.length()+1];   // dp[i] maps to dp[i][j], where i is the length of s, j is the length of j\n        char[] sStr = s.toCharArray();\n        char[] pStr = p.toCharArray();\n        dp[0] = true;   // before we started any iteration, dp[0] is equal to dp[0][0], meaning both s and p are EMPTY\n        for (int j=1; j<=pStr.length; j++) {\n            char pChr = pStr[j-1];\n            if (pChr == \'*\') {\n                // same optimization as complete backpack problem\n                // we scan from 1 to s.length, so that dp[i] = dp[i] || dp[i-1]\n                // just thinking like every time we iterating dp[i], the dp[i][j] we referenced is actually previous iteration\'s result. so dp[i-1] is actually dp[i-1][j] from previous step of current i-loop for string s, dp[i] is actually dp[i][j-1] from previous j-loop for string p\n                // it\'s relatively easy to understand that before the dp[i]\'s value is updated, dp[i] refers to dp[i][j-1] \n                // the hard to understand part may be why dp[i-1] equals to dp[i-1][j]. Notice dp[i-1]\'s value was updated in previous step\'s update (we update dp[i-1] in dp[i-2]\'s step), so dp[i-1] is equal to dp[i-1][j]\n                for (int i=1; i<=sStr.length; i++) {\n                    dp[i] = dp[i] || dp[i-1];\n                }\n            } else {\n                // same optimization as zero-one backpack\n                // dp[i-1] means dp[i-1][j-1]\n                for (int i=sStr.length; i>=1; i--) {\n                    if (sStr[i-1] == pChr || pChr == \'?\') {\n                        dp[i] = dp[i-1];\n                    } else {\n                        dp[i] = false;\n                    }\n                }\n                // now, after we see the first non-\'*\' character, as dp[0] means dp[i][0] where i>=1, dp[i][0] it\'s definite false (matching empty p with non-empty s)\n                // we want to set that value to false\n                dp[0] = false;\n            }\n        }\n        return dp[sStr.length];\n    }\n```
[]