算法面试大全-字符串总结

客官°小女子只卖身不卖艺 2022-10-17 13:50 168阅读 0赞

## 3、字符串 ##

### 3.1 基本概念 ###

(1)回文

(2)字串(连续)

(3)子序列(不连续)

(4)前缀树(trie树)

(5)后缀树和后缀数组

(6)匹配

(7)字典序

### 3.2 字符串匹配 ###

#### 3.2.1 暴力匹配 ####

public class BF {
        
        public int bf(String s1,String s2){
        
            int i=0;
            int j=0;
            while (i<s1.length()&&j<s2.length()){
        
                if (s1.charAt(i)==s2.charAt(j)){
        
                    i++;
                    j++;
                }
                else {
        
                    i = i - j + 1;   //查询字串向前移动，然后从i-j+1处重新匹配
                    j=0;
                }
            }
            if (j==s2.length()){
        
                return i-j;           //返回索引为i-j
            }
            else {
        
                return -1;
            }
        }
    }

#### 3.2.2 KMP 算法 ####

public class KMP {
        
        /**
         * KMP算法匹配问题
         * @param s1  主串
         * @param s2  模式串
         */
    
        public int kmp(String s1,String s2){
        
            char[]  strings1 = s1.toCharArray();
            char[]  strings2 = s2.toCharArray();
            int i=0;
            int j=0;
            int[] next=getNext2(s2);
            while (i<s1.length()&&j<s2.length()){
        
                if (j==-1||strings1[i]==strings2[j]){
        
                    i++;
                    j++;
                }
                else {
        
                      j=next[j];   // KMP算法的核心就是i不回退，j回退，j回退的位置为next[j]
                }
            }
            if (j==s2.length()){
        
                return i-j;
            }
            else {
        
                return -1;
            }
        }
    
        int[] getNext(String s){
        
            char[] p = s.toCharArray();
            int[] next=new int[p.length];
            next[0]=-1;
            int l=0;
            int k=-1;
            while (l<p.length-1){
        
                if (k==-1||p[l]==p[k]){
        
                    if (p[++l]==p[++k]){
        
                        next[l]=next[k];
                    }
                    else {
        
                        next[l]=k;
                    }
                }
                else {
        
                    k=next[k];
                }
            }
            return next;
        }
    
        int[] getNext2(String s){
        
            int[] next=new int[s.length()];
            next[0]=-1;
            int k=-1;
            int j=0;
            while(j<s.length()-1){
        
                if (k==-1||s.charAt(j)==s.charAt(k)){
        
                    j++;
                    k++;
                    next[j]=k;
                }
                else {
        
                    k=next[k];
                }
            }
            return next;
        }
    
    
        public static void main(String[] args) {
        
            String s1="ABCABCDHG";
            String s2="ABCABB";
            KMP kmp=new KMP();
            int match = kmp.kmp(s1, s2);
            System.out.println(match);
        }
    }

####  ####

### 经典题目源码 ###

#### [最长公共前缀][Link 1] ####

(1) 横向扫描

class Solution {
        
        public String longestCommonPrefix(String[] strs) {
        
            if (strs == null || strs.length == 0) {
        
                return "";
            }
            String prefix = strs[0];
            int count = strs.length;
            for (int i = 1; i < count; i++) {
        
                prefix = longestCommonPrefix(prefix, strs[i]);
                if (prefix.length() == 0) {
        
                    break;
                }
            }
            return prefix;
        }
    
        public String longestCommonPrefix(String str1, String str2) {
        
            int length = Math.min(str1.length(), str2.length());
            int index = 0;
            while (index < length && str1.charAt(index) == str2.charAt(index)) {
        
                index++;
            }
            return str1.substring(0, index);
        }
    }

(2) 纵向扫描

class Solution {
        public String longestCommonPrefix(String[] strs) {
            if (strs == null || strs.length == 0) {
                return "";
            }
            int length = strs[0].length();
            int count = strs.length;
            for (int i = 0; i < length; i++) {
                char c = strs[0].charAt(i);
                for (int j = 1; j < count; j++) {
                    if (i == strs[j].length() || strs[j].charAt(i) != c) {
                        return strs[0].substring(0, i);
                    }
                }
            }
            return strs[0];
        }
    }

(3) 分治

class Solution {
        
        public String longestCommonPrefix(String[] strs) {
        
            if (strs == null || strs.length == 0) {
        
                return "";
            } else {
        
                return longestCommonPrefix(strs, 0, strs.length - 1);
            }
        }
    
        public String longestCommonPrefix(String[] strs, int start, int end) {
        
            if (start == end) {
        
                return strs[start];
            } else {
        
                int mid = (end - start) / 2 + start;
                String lcpLeft = longestCommonPrefix(strs, start, mid);
                String lcpRight = longestCommonPrefix(strs, mid + 1, end);
                return commonPrefix(lcpLeft, lcpRight);
            }
        }
    
        public String commonPrefix(String lcpLeft, String lcpRight) {
        
            int minLength = Math.min(lcpLeft.length(), lcpRight.length());       
            for (int i = 0; i < minLength; i++) {
        
                if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
        
                    return lcpLeft.substring(0, i);
                }
            }
            return lcpLeft.substring(0, minLength);
        }
    }

(4) 二分查找

class Solution {
        
        public String longestCommonPrefix(String[] strs) {
        
            if (strs == null || strs.length == 0) {
        
                return "";
            }
            int minLength = Integer.MAX_VALUE;
            for (String str : strs) {
        
                minLength = Math.min(minLength, str.length());
            }
            int low = 0, high = minLength;
            while (low < high) {
        
                int mid = (high - low + 1) / 2 + low;
                if (isCommonPrefix(strs, mid)) {
        
                    low = mid;
                } else {
        
                    high = mid - 1;
                }
            }
            return strs[0].substring(0, low);
        }
    
        public boolean isCommonPrefix(String[] strs, int length) {
        
            String str0 = strs[0].substring(0, length);
            int count = strs.length;
            for (int i = 1; i < count; i++) {
        
                String str = strs[i];
                for (int j = 0; j < length; j++) {
        
                    if (str0.charAt(j) != str.charAt(j)) {
        
                        return false;
                    }
                }
            }
            return true;
        }
    }

#### [最长回文子串][Link 2] ####

(1) 动态规划

class Solution {
        
        public String longestPalindrome(String s) {
        
            int n = s.length();
            boolean[][] dp = new boolean[n][n];
            String ans = "";
            for (int l = 0; l < n; ++l) {
        
                for (int i = 0; i + l < n; ++i) {
        
                    int j = i + l;
                    if (l == 0) {
        
                        dp[i][j] = true;
                    } else if (l == 1) {
        
                        dp[i][j] = (s.charAt(i) == s.charAt(j));
                    } else {
        
                        dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
                    }
                    if (dp[i][j] && l + 1 > ans.length()) {
        
                        ans = s.substring(i, i + l + 1);
                    }
                }
            }
            return ans;
        }
    }
    
        public static String longestPalindromedp(String s) {
        
            if (s.isEmpty()) {
        
                return s;
            }
            int n = s.length();
            boolean[][] dp = new boolean[n][n];
            int left = 0;
            int right = 0;
            for (int i = n - 2; i >= 0; i--) {
        
                dp[i][i] = true;
                for (int j = i + 1; j < n; j++) {
        
                    dp[i][j] = s.charAt(i) == s.charAt(j) &&( j-i<3||dp[i+1][j-1]);//小于3是因为aba一定是回文
                    if(dp[i][j]&&right-left<j-i){
        
                        left=i;
                        right=j;
                    }
                }
            }
            return s.substring(left,right+1);
        }

(2) 中心扩展算法

class Solution {
        
        public String longestPalindrome(String s) {
        
            if (s == null || s.length() < 1) {
        
                return "";
            }
            int start = 0, end = 0;
            for (int i = 0; i < s.length(); i++) {
        
                int len1 = expandAroundCenter(s, i, i);
                int len2 = expandAroundCenter(s, i, i + 1);
                int len = Math.max(len1, len2);
                if (len > end - start) {
        
                    start = i - (len - 1) / 2;
                    end = i + len / 2;
                }
            }
            return s.substring(start, end + 1);
        }
    
        public int expandAroundCenter(String s, int left, int right) {
        
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        
                --left;
                ++right;
            }
            return right - left - 1;
        }
    }

#### [最长回文子序列][Link 3] ####

class Solution {
        
        public int longestPalindromeSubseq(String s) {
        
            int n = s.length();
            int[][] f = new int[n][n];
            for (int i = n - 1; i >= 0; i--) {
        
                f[i][i] = 1;
                for (int j = i + 1; j < n; j++) {
        
                    if (s.charAt(i) == s.charAt(j)) {
        
                        f[i][j] = f[i + 1][j - 1] + 2;
                    } else {
        
                        f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                    }
                }
            }
            return f[0][n - 1];
        }
    }

#### [最小覆盖子串][Link 4] ####

滑动窗口

class Solution {
        
        Map<Character, Integer> ori = new HashMap<Character, Integer>();
        Map<Character, Integer> cnt = new HashMap<Character, Integer>();
    
        public String minWindow(String s, String t) {
        
            int tLen = t.length();
            for (int i = 0; i < tLen; i++) {
        
                char c = t.charAt(i);
                ori.put(c, ori.getOrDefault(c, 0) + 1);
            }
            int l = 0, r = -1;
            int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
            int sLen = s.length();
            while (r < sLen) {
        
                ++r;
                if (r < sLen && ori.containsKey(s.charAt(r))) {
        
                    cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
                }
                while (check() && l <= r) {
        
                    if (r - l + 1 < len) {
        
                        len = r - l + 1;
                        ansL = l;
                        ansR = l + len;
                    }
                    if (ori.containsKey(s.charAt(l))) {
        
                        cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
                    }
                    ++l;
                }
            }
            return ansL == -1 ? "" : s.substring(ansL, ansR);
        }
    
        public boolean check() {
        
            Iterator iter = ori.entrySet().iterator(); 
            while (iter.hasNext()) {
         
                Map.Entry entry = (Map.Entry) iter.next(); 
                Character key = (Character) entry.getKey(); 
                Integer val = (Integer) entry.getValue(); 
                if (cnt.getOrDefault(key, 0) < val) {
        
                    return false;
                }
            } 
            return true;
        }
    }

#### [无重复字符的最长子串][Link 5] ####

滑动窗口

class Solution {
        
        public int lengthOfLongestSubstring(String s) {
        
            // 哈希集合，记录每个字符是否出现过
            Set<Character> occ = new HashSet<Character>();
            int n = s.length();
            // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
            int rk = -1, ans = 0;
            for (int i = 0; i < n; ++i) {
        
                if (i != 0) {
        
                    // 左指针向右移动一格，移除一个字符
                    occ.remove(s.charAt(i - 1));
                }
                while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
        
                    // 不断地移动右指针
                    occ.add(s.charAt(rk + 1));
                    ++rk;
                }
                // 第 i 到 rk 个字符是一个极长的无重复字符子串
                ans = Math.max(ans, rk - i + 1);
            }
            return ans;
        }
    }

#### [实现 strStr()][strStr] ####

方法一：子串逐一比较 - 线性时间复杂度

class Solution {
        
      public int strStr(String haystack, String needle) {
        
        int L = needle.length(), n = haystack.length();
    
        for (int start = 0; start < n - L + 1; ++start) {
        
          if (haystack.substring(start, start + L).equals(needle)) {
        
            return start;
          }
        }
        return -1;
      }
    }

方法二：双指针 - 线性时间复杂度

class Solution {
        
      public int strStr(String haystack, String needle) {
        
        int L = needle.length(), n = haystack.length();
        if (L == 0) return 0;
    
        int pn = 0;
        while (pn < n - L + 1) {
        
          // find the position of the first needle character
          // in the haystack string
          while (pn < n - L + 1 && haystack.charAt(pn) != needle.charAt(0)) ++pn;
    
          // compute the max match string
          int currLen = 0, pL = 0;
          while (pL < L && pn < n && haystack.charAt(pn) == needle.charAt(pL)) {
        
            ++pn;
            ++pL;
            ++currLen;
          }
          // if the whole needle string is found,
          // return its start position
          if (currLen == L) return pn - L;
    
          // otherwise, backtrack
          pn = pn - currLen + 1;
        }
        return -1;
      }
    }

#### [计算器][Link 6] ####

class Solution {
        
        public int calculate(String s) {
        
            char[] cs = s.trim().toCharArray();
            Stack<Integer> st = new Stack();
            int ans = 0, i = 0;
            while(i < cs.length){
        
                if(cs[i] == ' ') {
        i++;continue;}
                char tmp = cs[i];
                if(tmp == '*' || tmp == '/' || tmp == '+' || tmp == '-'){
        
                    i++;
                    while(i < cs.length && cs[i] == ' ') i++;
                }
                int num = 0;
                while(i < cs.length && Character.isDigit(cs[i])){
        
                    num = num * 10 + cs[i] - '0';
                    i++;
                }
                switch(tmp){
        
                    case '-':
                        num = -num;
                        break;
                    case '*':
                        num = st.pop() * num;
                        break;
                    case '/':
                        num = st.pop() / num;
                        break;
                    default:
                        break;
                }
                st.push(num);
            }
            while(!st.isEmpty()) ans += st.pop();
            return ans;
        }
    
        
    }

[基本计算器 II][II]

#### [最长有效括号][Link 7] ####

方法一：动态规划

public class Solution {
        
        public int longestValidParentheses(String s) {
        
            int maxans = 0;
            int[] dp = new int[s.length()];
            for (int i = 1; i < s.length(); i++) {
        
                if (s.charAt(i) == ')') {
        
                    if (s.charAt(i - 1) == '(') {
        
                        dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                    } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
        
                        dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                    }
                    maxans = Math.max(maxans, dp[i]);
                }
            }
            return maxans;
        }
    }

方法二：栈

public class Solution {
        
        public int longestValidParentheses(String s) {
        
            int maxans = 0;
            Deque<Integer> stack = new LinkedList<Integer>();
            stack.push(-1);
            for (int i = 0; i < s.length(); i++) {
        
                if (s.charAt(i) == '(') {
        
                    stack.push(i);
                } else {
        
                    stack.pop();
                    if (stack.empty()) {
        
                        stack.push(i);
                    } else {
        
                        maxans = Math.max(maxans, i - stack.peek());
                    }
                }
            }
            return maxans;
        }
    }

方法三：不需要额外的空间

public class Solution {
        
        public int longestValidParentheses(String s) {
        
            int left = 0, right = 0, maxlength = 0;
            for (int i = 0; i < s.length(); i++) {
        
                if (s.charAt(i) == '(') {
        
                    left++;
                } else {
        
                    right++;
                }
                if (left == right) {
        
                    maxlength = Math.max(maxlength, 2 * right);
                } else if (right > left) {
        
                    left = right = 0;
                }
            }
            left = right = 0;
            for (int i = s.length() - 1; i >= 0; i--) {
        
                if (s.charAt(i) == '(') {
        
                    left++;
                } else {
        
                    right++;
                }
                if (left == right) {
        
                    maxlength = Math.max(maxlength, 2 * left);
                } else if (left > right) {
        
                    left = right = 0;
                }
            }
            return maxlength;
        }
    }

#### [有效的括号][Link 8] ####

class Solution {
        
        public boolean isValid(String s) {
        
            int n = s.length();
            if (n % 2 == 1) {
        
                return false;
            }
    
            Map<Character, Character> pairs = new HashMap<Character, Character>() {
        {
        
                put(')', '(');
                put(']', '[');
                put('}', '{');
            }};
            Deque<Character> stack = new LinkedList<Character>();
            for (int i = 0; i < n; i++) {
        
                char ch = s.charAt(i);
                if (pairs.containsKey(ch)) {
        
                    if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
        
                        return false;
                    }
                    stack.pop();
                } else {
        
                    stack.push(ch);
                }
            }
            return stack.isEmpty();
        }
    }

#### [括号生成][Link 9] ####

方法一：暴力法

class Solution {
        
        public List<String> generateParenthesis(int n) {
        
            List<String> combinations = new ArrayList<String>();
            generateAll(new char[2 * n], 0, combinations);
            return combinations;
        }
    
        public void generateAll(char[] current, int pos, List<String> result) {
        
            if (pos == current.length) {
        
                if (valid(current)) {
        
                    result.add(new String(current));
                }
            } else {
        
                current[pos] = '(';
                generateAll(current, pos + 1, result);
                current[pos] = ')';
                generateAll(current, pos + 1, result);
            }
        }
    
        public boolean valid(char[] current) {
        
            int balance = 0;
            for (char c: current) {
        
                if (c == '(') {
        
                    ++balance;
                } else {
        
                    --balance;
                }
                if (balance < 0) {
        
                    return false;
                }
            }
            return balance == 0;
        }
    }

方法二：回溯法

class Solution {
        
        public List<String> generateParenthesis(int n) {
        
            List<String> ans = new ArrayList<String>();
            backtrack(ans, new StringBuilder(), 0, 0, n);
            return ans;
        }
    
        public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        
            if (cur.length() == max * 2) {
        
                ans.add(cur.toString());
                return;
            }
            if (open < max) {
        
                cur.append('(');
                backtrack(ans, cur, open + 1, close, max);
                cur.deleteCharAt(cur.length() - 1);
            }
            if (close < open) {
        
                cur.append(')');
                backtrack(ans, cur, open, close + 1, max);
                cur.deleteCharAt(cur.length() - 1);
            }
        }
    }

#### [反转字符串][Link 10] ####

方法一：双指针

class Solution {
        
        public void reverseString(char[] s) {
        
            int n = s.length;
            for (int left = 0, right = n - 1; left < right; ++left, --right) {
        
                char tmp = s[left];
                s[left] = s[right];
                s[right] = tmp;
            }
        }
    }

方法二:栈

public String reverse5(String str) {
          
        if (str == null || str.length() <= 1) {
          
            return str;  
        }  
        String result = "";  
        char[] arr = str.toCharArray();  
        Stack<Character> stack = new Stack<Character>();  
        for (char a : arr) {
          
            stack.push(a);  
        }  
        int length = stack.size();  
        //注意这个地方必须要先把length暂存起来，因为在遍历的过程中，pop()堆的时候，会改变堆的大小。  
        for (int i = 0; i < length; i++) {
          
            result += stack.pop();  
        }  
        return result;  
    }

#### [编辑距离][Link 11] ####

class Solution {
        
        public int minDistance(String word1, String word2) {
        
            int n = word1.length();
            int m = word2.length();
    
            // 有一个字符串为空串
            if (n * m == 0) {
        
                return n + m;
            }
    
            // DP 数组
            int[][] D = new int[n + 1][m + 1];
    
            // 边界状态初始化
            for (int i = 0; i < n + 1; i++) {
        
                D[i][0] = i;
            }
            for (int j = 0; j < m + 1; j++) {
        
                D[0][j] = j;
            }
    
            // 计算所有 DP 值
            for (int i = 1; i < n + 1; i++) {
        
                for (int j = 1; j < m + 1; j++) {
        
                    int left = D[i - 1][j] + 1;
                    int down = D[i][j - 1] + 1;
                    int left_down = D[i - 1][j - 1];
                    if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
        
                        left_down += 1;
                    }
                    D[i][j] = Math.min(left, Math.min(down, left_down));
                }
            }
            return D[n][m];
        }
    }

#### [电话号码的字母组合][Link 12] ####

class Solution {
        
        public List<String> letterCombinations(String digits) {
        
            List<String> combinations = new ArrayList<String>();
            if (digits.length() == 0) {
        
                return combinations;
            }
            Map<Character, String> phoneMap = new HashMap<Character, String>() {
        {
        
                put('2', "abc");
                put('3', "def");
                put('4', "ghi");
                put('5', "jkl");
                put('6', "mno");
                put('7', "pqrs");
                put('8', "tuv");
                put('9', "wxyz");
            }};
            backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
            return combinations;
        }
    
        public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        
            if (index == digits.length()) {
        
                combinations.add(combination.toString());
            } else {
        
                char digit = digits.charAt(index);
                String letters = phoneMap.get(digit);
                int lettersCount = letters.length();
                for (int i = 0; i < lettersCount; i++) {
        
                    combination.append(letters.charAt(i));
                    backtrack(combinations, phoneMap, digits, index + 1, combination);
                    combination.deleteCharAt(index);
                }
            }
        }
    }

#### [通配符匹配][Link 13] ####

方法一：动态规划

class Solution {
        
        public boolean isMatch(String s, String p) {
        
            int m = s.length();
            int n = p.length();
            boolean[][] dp = new boolean[m + 1][n + 1];
            dp[0][0] = true;
            for (int i = 1; i <= n; ++i) {
        
                if (p.charAt(i - 1) == '*') {
        
                    dp[0][i] = true;
                } else {
        
                    break;
                }
            }
            for (int i = 1; i <= m; ++i) {
        
                for (int j = 1; j <= n; ++j) {
        
                    if (p.charAt(j - 1) == '*') {
        
                        dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                    } else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
        
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
            return dp[m][n];
        }
    }

方法二：贪心算法

class Solution {
        
        public boolean isMatch(String s, String p) {
        
            int sRight = s.length(), pRight = p.length();
            while (sRight > 0 && pRight > 0 && p.charAt(pRight - 1) != '*') {
        
                if (charMatch(s.charAt(sRight - 1), p.charAt(pRight - 1))) {
        
                    --sRight;
                    --pRight;
                } else {
        
                    return false;
                }
            }
    
            if (pRight == 0) {
        
                return sRight == 0;
            }
    
            int sIndex = 0, pIndex = 0;
            int sRecord = -1, pRecord = -1;
            
            while (sIndex < sRight && pIndex < pRight) {
        
                if (p.charAt(pIndex) == '*') {
        
                    ++pIndex;
                    sRecord = sIndex;
                    pRecord = pIndex;
                } else if (charMatch(s.charAt(sIndex), p.charAt(pIndex))) {
        
                    ++sIndex;
                    ++pIndex;
                } else if (sRecord != -1 && sRecord + 1 < sRight) {
        
                    ++sRecord;
                    sIndex = sRecord;
                    pIndex = pRecord;
                } else {
        
                    return false;
                }
            }
    
            return allStars(p, pIndex, pRight);
        }
    
        public boolean allStars(String str, int left, int right) {
        
            for (int i = left; i < right; ++i) {
        
                if (str.charAt(i) != '*') {
        
                    return false;
                }
            }
            return true;
        }
    
        public boolean charMatch(char u, char v) {
        
            return u == v || v == '?';
        }
    }

#### [正则表达式匹配][Link 14] ####

方法一：动态规划

class Solution {
        
        public boolean isMatch(String s, String p) {
        
            int m = s.length();
            int n = p.length();
    
            boolean[][] f = new boolean[m + 1][n + 1];
            f[0][0] = true;
            for (int i = 0; i <= m; ++i) {
        
                for (int j = 1; j <= n; ++j) {
        
                    if (p.charAt(j - 1) == '*') {
        
                        f[i][j] = f[i][j - 2];
                        if (matches(s, p, i, j - 1)) {
        
                            f[i][j] = f[i][j] || f[i - 1][j];
                        }
                    }
                    else {
        
                        if (matches(s, p, i, j)) {
        
                            f[i][j] = f[i - 1][j - 1];
                        }
                    }
                }
            }
            return f[m][n];
        }
    
        public boolean matches(String s, String p, int i, int j) {
        
            if (i == 0) {
        
                return false;
            }
            if (p.charAt(j - 1) == '.') {
        
                return true;
            }
            return s.charAt(i - 1) == p.charAt(j - 1);
        }
    }

#### [单词距离][Link 15] ####

class Solution {
        
        public int findClosest(String[] words, String word1, String word2) {
        
            HashMap<String,List<Integer>> map = new HashMap<>();
            //构造哈希表
            for(int i=0;i<words.length;i++){
        
                List<Integer> list = map.getOrDefault(words[i],new ArrayList<>());
                list.add(i);
                map.put(words[i], list);
            }
            List<Integer> l1 = map.get(word1);
            List<Integer> l2 = map.get(word2);
            int i=0;
            int j=0;
            int min = Integer.MAX_VALUE;
            while(i<l1.size()&&j<l2.size()){
        
                int curr1 = l1.get(i);
                int curr2 = l2.get(j);
                min = Math.min(min,Math.abs(curr1-curr2));
                if(curr1<curr2){
        
                    i++;
                }else{
        
                    j++;
                }
            }
            return min;
        }
    }

#### [查找和替换模式][Link 16] ####

方法一：双映射表

class Solution {
        
        public List<String> findAndReplacePattern(String[] words, String pattern) {
        
            List<String> ans = new ArrayList();
            for (String word: words)
                if (match(word, pattern))
                    ans.add(word);
            return ans;
        }
    
        public boolean match(String word, String pattern) {
        
            Map<Character, Character> m1 = new HashMap();
            Map<Character, Character> m2 = new HashMap();
    
            for (int i = 0; i < word.length(); ++i) {
        
                char w = word.charAt(i);
                char p = pattern.charAt(i);
                if (!m1.containsKey(w)) m1.put(w, p);
                if (!m2.containsKey(p)) m2.put(p, w);
                if (m1.get(w) != p || m2.get(p) != w)
                    return false;
            }
    
            return true;
        }
    }

方法二：单映射表

class Solution {
        
        public List<String> findAndReplacePattern(String[] words, String pattern) {
        
            List<String> ans = new ArrayList();
            for (String word: words)
                if (match(word, pattern))
                    ans.add(word);
            return ans;
        }
    
        public boolean match(String word, String pattern) {
        
            Map<Character, Character> M = new HashMap();
            for (int i = 0; i < word.length(); ++i) {
        
                char w = word.charAt(i);
                char p = pattern.charAt(i);
                if (!M.containsKey(w)) M.put(w, p);
                if (M.get(w) != p) return false;
            }
    
            boolean[] seen = new boolean[26];
            for (char p: M.values()) {
        
                if (seen[p - 'a']) return false;
                seen[p - 'a'] = true;
            }
            return true;
        }
    }

#### [括号的最大嵌套深度][Link 17] ####

class Solution {
        
        public int maxDepth(String s) {
        
            Deque<Character> stack = new LinkedList<>();
            char[] arr = s.toCharArray();
            int len = arr.length;
            if(len==0){
        
                return 0;
            }
            int max=0;
            for(char c: arr){
        
                if(c==')'){
        
                    stack.pollLast();
                }else if(c=='('){
        
                    stack.offer(c);
                }
                max = Math.max(max,stack.size());
            }
            return max;
        }
    }

#### [单词搜索][Link 18] ####

class Solution {
        
        public boolean exist(char[][] board, String word) {
        
            int h = board.length, w = board[0].length;
            boolean[][] visited = new boolean[h][w];
            for (int i = 0; i < h; i++) {
        
                for (int j = 0; j < w; j++) {
        
                    boolean flag = check(board, visited, i, j, word, 0);
                    if (flag) {
        
                        return true;
                    }
                }
            }
            return false;
        }
    
        public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
        
            if (board[i][j] != s.charAt(k)) {
        
                return false;
            } else if (k == s.length() - 1) {
        
                return true;
            }
            visited[i][j] = true;
            int[][] directions = {
        {
        0, 1}, {
        0, -1}, {
        1, 0}, {
        -1, 0}};
            boolean result = false;
            for (int[] dir : directions) {
        
                int newi = i + dir[0], newj = j + dir[1];
                if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
        
                    if (!visited[newi][newj]) {
        
                        boolean flag = check(board, visited, newi, newj, s, k + 1);
                        if (flag) {
        
                            result = true;
                            break;
                        }
                    }
                }
            }
            visited[i][j] = false;
            return result;
        }
    }

#### 合并K个排序过的链表 ####

ListNode mergeKListNode(ArrayList<ListNode> k){
        
            if(k.size()==0){
        
                return null;
            }
            return mergeHelper(k,0,k.size()-1);
        }
        ListNode mergeHelper(List<ListNode> lists,int start,int end){
        
            if(start == end){
        
                return lists.get(start);
            }
            int mid = start + ( end - start )/2;
            ListNode left = mergeHelper(lists, start, mid);
            ListNode right = mergeHelper(lists, mid+1, end);
            return mergeTwoLists(left,right);
        }
        ListNode mergeTwoLists(ListNode list1,ListNode list2){
        
            ListNode dummy = new ListNode(0);
            ListNode tail = dummy;
            while(list1!=null&&list2!=null){
        
                if(list1.val<list2.val){
        
                    tail.next = list1;
                    tail = tail.next;
                    list1 = list1.next;
                }else{
        
                    tail.next = list2;
                    tail = list2;
                    list2 = list2.next;
                }
            }
            if(list1!=null){
        
                tail.next = list1;
            }else{
        
                tail.next = list2;
            }
            return dummy.next;
        }

[Link 1]: https://leetcode-cn.com/problems/longest-common-prefix/
[Link 2]: https://leetcode-cn.com/problems/longest-palindromic-substring/
[Link 3]: https://leetcode-cn.com/problems/longest-palindromic-subsequence/
[Link 4]: https://leetcode-cn.com/problems/minimum-window-substring/
[Link 5]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[strStr]: https://leetcode-cn.com/problems/implement-strstr/
[Link 6]: https://leetcode-cn.com/problems/calculator-lcci/
[II]: https://leetcode-cn.com/problems/basic-calculator-ii/
[Link 7]: https://leetcode-cn.com/problems/longest-valid-parentheses/
[Link 8]: https://leetcode-cn.com/problems/valid-parentheses/
[Link 9]: https://leetcode-cn.com/problems/generate-parentheses/
[Link 10]: https://leetcode-cn.com/problems/reverse-string/
[Link 11]: https://leetcode-cn.com/problems/edit-distance/
[Link 12]: https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
[Link 13]: https://leetcode-cn.com/problems/wildcard-matching/
[Link 14]: https://leetcode-cn.com/problems/regular-expression-matching/
[Link 15]: https://leetcode-cn.com/problems/find-closest-lcci/
[Link 16]: https://leetcode-cn.com/problems/find-and-replace-pattern/
[Link 17]: https://leetcode-cn.com/problems/maximum-nesting-depth-of-the-parentheses/
[Link 18]: https://leetcode-cn.com/problems/word-search/