algorithm004-03 · kelly422 · Dec 12, 2019 · Dec 8, 2019 · Dec 10, 2019
diff --git a/Week 08/id_388/LeeCode_388_10.java b/Week 08/id_388/LeeCode_388_10.java
@@ -0,0 +1,100 @@
+package com.company.leetcode.editor.cn;//给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
+//
+// '.' 匹配任意单个字符
+//'*' 匹配零个或多个前面的那一个元素
+//
+//
+// 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
+//
+// 说明:
+//
+//
+// s 可能为空，且只包含从 a-z 的小写字母。
+// p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
+//
+//
+// 示例 1:
+//
+// 输入:
+//s = "aa"
+//p = "a"
+//输出: false
+//解释: "a" 无法匹配 "aa" 整个字符串。
+//
+//
+// 示例 2:
+//
+// 输入:
+//s = "aa"
+//p = "a*"
+//输出: true
+//解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
+//
+//
+// 示例 3:
+//
+// 输入:
+//s = "ab"
+//p = ".*"
+//输出: true
+//解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
+//
+//
+// 示例 4:
+//
+// 输入:
+//s = "aab"
+//p = "c*a*b"
+//输出: true
+//解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
+//
+//
+// 示例 5:
+//
+// 输入:
+//s = "mississippi"
+//p = "mis*is*p*."
+//输出: false
+// Related Topics 字符串 动态规划 回溯算法
+
+
+
+//leetcode submit region begin(Prohibit modification and deletion)
+class Solution_10 {
+    public boolean isMatch(String s, String p) {
+        if (s == null || p == null) {
+            return false;
+        }
+        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
+        dp[0][0] = true;
+        for (int i = 0; i < p.length(); i++) {
+            if (p.charAt(i) == '*' && dp[0][i - 1]) {
+                dp[0][i + 1] = true;
+            }
+        }
+        for (int i = 0; i < s.length(); i++) {
+            for (int j = 0; j < p.length(); j++) {
+                if (p.charAt(j) == '.') {
+                    dp[i + 1][j + 1] = dp[i][j];
+                }
+                if (p.charAt(j) == s.charAt(i)) {
+                    dp[i + 1][j + 1] = dp[i][j];
+                }
+                if (p.charAt(j) == '*') {
+                    if (p.charAt(j-1) != s.charAt(i) && p.charAt(j - 1) != '.') {
+                        dp[i + 1][j + 1] = dp[i + 1][j - 1];
+                    } else {
+                        dp[i + 1][j + 1] = (dp[i + 1][j] || dp[i][j + 1] || dp[i + 1][j - 1]);
+                    }
+                }
+            }
+        }
+        return dp[s.length()][p.length()];
+    }
+
+//    public static void main(String[] args) {
+//        Solution s = new Solution();
+//        s.isMatch("aa","a");
+//    }
+}
+//leetcode submit region end(Prohibit modification and deletion)
diff --git a/Week 08/id_388/LeeCode_388_1143.java b/Week 08/id_388/LeeCode_388_1143.java
@@ -0,0 +1,103 @@
+package com.company.leetcode.editor.cn;
+
+//给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。
+//count = 2
+// 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
+//例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
+//
+// 若这两个字符串没有公共子序列，则返回 0。
+//
+//
+//
+// 示例 1:
+//
+// 输入：text1 = "abcde", text2 = "ace"
+//输出：3
+//解释：最长公共子序列是 "ace"，它的长度为 3。
+//
+//
+// 示例 2:
+//
+// 输入：text1 = "abc", text2 = "abc"
+//输出：3
+//解释：最长公共子序列是 "abc"，它的长度为 3。
+//
+//
+// 示例 3:
+//
+// 输入：text1 = "abc", text2 = "def"
+//输出：0
+//解释：两个字符串没有公共子序列，返回 0。
+//
+//
+//
+//
+// 提示:
+//
+//
+// 1 <= text1.length <= 1000
+// 1 <= text2.length <= 1000
+// 输入的字符串只含有小写英文字符。
+//
+// Related Topics 动态规划
+
+
+
+//leetcode submit region begin(Prohibit modification and deletion)
+class Solution_1143 {
+
+    public int longestCommonSubsequence(String text1, String text2) {
+
+        char[] c1 = text1.toCharArray();
+        char[] c2 = text2.toCharArray();
+
+        if (c1.length < 1 || c2.length < 1) {
+            return 0;
+        }
+
+        int[][] dp = new int[c1.length][c2.length];
+        dp[0][0] = c1[0] == c2[0] ? 1 : 0;
+        //row0
+        for (int i = 1; i < c2.length; i++) {
+            if (c1[0] == c2[i]) {
+                dp[0][i] =  1;
+            } else {
+                dp[0][i] = dp[0][i - 1];
+            }
+        }
+        //col0
+        for (int j = 1; j < c1.length; j++) {
+            if (c1[j] == c2[0]) {
+                dp[j][0] = 1;
+            } else {
+                dp[j][0] = dp[j - 1][0];
+            }
+        }
+
+        for (int i = 1; i < c1.length; i++) {
+            for (int j = 1; j < c2.length; j++) {
+                if (c1[i] == c2[j]) {
+                    dp[i][j] = dp[i - 1][j - 1] + 1;
+                } else {
+                    dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
+                }
+            }
+        }
+
+        return dp[c1.length - 1][c2.length - 1];
+    }
+
+
+//    public static void main(String[] args) {
+//        Solution s = new Solution();
+//        String text1 = "dknkdizqxkdczafixidorgfcnkrirmhmzqbcfuvojsxwraxe";
+//        String text2 = "dulixqfgvipenkfubgtyxujixspoxmhgvahqdmzmlyhajerqz";
+//        //Wrong Answer: input:"bsbininm" "jmjkbkjkv" Output:2 Expected:1
+//        //Wrong Answer: input:"dknkdizqxkdczafixidorgfcnkrirmhmzqbcfuvojsxwraxe"
+//        // "dulixqfgvipenkfubgtyxujixspoxmhgvahqdmzmlyhajerqz"
+//        // Output:15 Expected:14
+//        int len = s.longestCommonSubsequence(text1,text2);
+//        System.out.println(len);
+//    }
+}
+//leetcode submit region end(Prohibit modification and deletion)
diff --git a/Week 08/id_388/LeeCode_388_115.java b/Week 08/id_388/LeeCode_388_115.java
@@ -0,0 +1,76 @@
+package com.company.leetcode.editor.cn;
+
+//给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。
+//
+// 一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
+// count = 2
+// 示例 1:
+//
+// 输入: S = "rabbbit", T = "rabbit"
+//输出: 3
+//解释:
+//
+//如下图所示, 有 3 种可以从 S 中得到 "rabbit" 的方案。
+//(上箭头符号 ^ 表示选取的字母)
+//
+//rabbbit
+//^^^^ ^^
+//rabbbit
+//^^ ^^^^
+//rabbbit
+//^^^ ^^^
+//
+//
+// 示例 2:
+//
+// 输入: S = "babgbag", T = "bag"
+//输出: 5
+//解释:
+//
+//如下图所示, 有 5 种可以从 S 中得到 "bag" 的方案。
+//(上箭头符号 ^ 表示选取的字母)
+//
+//babgbag
+//^^ ^
+//babgbag
+//^^    ^
+//babgbag
+//^    ^^
+//babgbag
+//  ^  ^^
+//babgbag
+//    ^^^
+// Related Topics 字符串 动态规划
+
+
+
+//leetcode submit region begin(Prohibit modification and deletion)
+class Solution_115 {
+    public int numDistinct(String s, String t) {
+        int rows = s.length();
+        int cols = t.length();
+        int[][] dp = new int[rows + 1][cols + 1];
+        dp[0][0] = 1;
+        for (int i = 1; i <= cols; i++) {
+            dp[0][i] = 1;
+        }
+        for (int i = 1; i <= rows; i++) {
+            for (int j = 1; j <= cols; j++) {
+                if (s.charAt(i - 1) == t.charAt(j - 1)) {
+                    dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
+                } else {
+                    dp[i][j] = dp[i][j - 1];
+                }
+            }
+        }
+        return dp[rows][cols];
+    }
+
+//    public static void main(String[] args) {
+//        Solution s = new Solution();
+//        String S = "babgbag";
+//        String T = "bag";
+//        System.out.println(s.numDistinct(S,T));
+//    }
+}
+//leetcode submit region end(Prohibit modification and deletion)
diff --git a/Week 08/id_388/LeeCode_388_125.java b/Week 08/id_388/LeeCode_388_125.java
@@ -0,0 +1,76 @@
+package com.company.leetcode.editor.cn;
+//给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
+//
+// 说明：本题中，我们将空字符串定义为有效的回文串。
+//
+// 示例 1:
+//
+// 输入: "A man, a plan, a canal: Panama"
+//输出: true
+//
+//
+// 示例 2:
+//
+// 输入: "race a car"
+//输出: false
+//
+// Related Topics 双指针 字符串
+
+
+
+//leetcode submit region begin(Prohibit modification and deletion)
+class Solution_125 {
+    public boolean isPalindrome(String s) {
+        if (s == null) {
+            return false;
+        }
+        if (s.length() == 1) {
+            return true;
+        }
+
+        int left = 0;
+        int right = s.length() - 1;
+        while (left < right) {
+            char leftChar = s.charAt(left);
+            while (left < right && !isValidChar(leftChar)) {
+                left++;
+                leftChar = s.charAt(left);
+            }
+            if (left == right) {
+                return true;
+            }
+            char rightChar = s.charAt(right);
+            while (left < right && !isValidChar(rightChar)){
+                right--;
+                rightChar = s.charAt(right);
+            }
+            if (left == right) {
+                return true;
+            }
+            String leftStr = String.valueOf(leftChar);
+            String rightStr = String.valueOf(rightChar);
+            if (!leftStr.equalsIgnoreCase(rightStr)){
+                return false;
+            }
+            left++;
+            right--;
+        }
+
+        return true;
+
+    }
+
+    //字母和数字字符
+    private boolean isValidChar(char c){
+        boolean b = (c >= '0' && c <= '9')
+                || (c >= 'A' && c <= 'Z')
+                || (c >= 'a' && c <= 'z');
+        return b;
+    }
+
+//    public static void main(String[] args) {
+//        Solution s = new Solution();
+//        System.out.println(s.isPalindrome("race a car"));
+//    }
+}
+//leetcode submit region end(Prohibit modification and deletion)