package y2019.Algorithm.str.hard;

import java.util.Stack;

/**

 * @ProjectName: cutter-point

 * @Package: y2019.Algorithm.str.hard

 * @ClassName: LongestValidParentheses

 * @Author: xiaof

 * @Description: 32. Longest Valid Parentheses

 *

 * Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

 *

 * Example 1:

 *

 * Input: "(()"

 * Output: 2

 * Explanation: The longest valid parentheses substring is "()"

 * Example 2:

 *

 * Input: ")()())"

 * Output: 4

 * Explanation: The longest valid parentheses substring is "()()"

 *

 * 求最长有效括号对，那么就是要确保子串是连续

 * @Date: 2019/8/6 9:51

 * @Version: 1.0

 */

public class LongestValidParentheses {

    public int solution(String s) {

        //用来统计最大的括号数，我们只要能匹配成功就行

        Stack<Integer> stack = new Stack();

        char[] ss = s.toCharArray();

        int n = ss.length, res = 0;

        //遍历

        for (int i = 0; i < ss.length; ++i) {

            if (ss[i] == '(') {

                stack.push(i); //用来存放int位置

            } else {

                if (!stack.isEmpty()) {

                    //如果不为空，那么就可以进行匹配

                    if (ss[stack.peek()] == '(') stack.pop();

                    else stack.push(i);

                } else {

                    stack.push(i);

                }

            }

        }

        //我们只需要统计剩下无法匹配的连续的（的数据比较就可以了

        //如果栈为空，那么正好完全匹配

        if (stack.isEmpty()) {

            res = n;

        } else {

            //如果不是完全匹配，那么就要计算连续两个(的间隔

            int r = n, l = 0;

            while (!stack.isEmpty()) {

                //不断获取最后的结束符号位置

                l = stack.pop();

                //取最长的串位置

                res = Math.max(r - l - 1, res);

                r = l; //更新位置

            }

            //最后还要判断从起始位置开始到当前位置消掉的长度

            res = Math.max(r, res);

        }

        return res;

    }

}

package y2019.Algorithm.str.hard;

/**

 * @ProjectName: cutter-point

 * @Package: y2019.Algorithm.str.hard

 * @ClassName: MinDistance

 * @Author: xiaof

 * @Description: 72. Edit Distance

 * Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

 *

 * You have the following 3 operations permitted on a word:

 *

 * Insert a character

 * Delete a character

 * Replace a character

 * Example 1:

 *

 * Input: word1 = "horse", word2 = "ros"

 * Output: 3

 * Explanation:

 * horse -> rorse (replace 'h' with 'r')

 * rorse -> rose (remove 'r')

 * rose -> ros (remove 'e')

 * Example 2:

 *

 * Input: word1 = "intention", word2 = "execution"

 * Output: 5

 * Explanation:

 * intention -> inention (remove 't')

 * inention -> enention (replace 'i' with 'e')

 * enention -> exention (replace 'n' with 'x')

 * exention -> exection (replace 'n' with 'c')

 * exection -> execution (insert 'u')

 * @Date: 2019/8/7 11:42

 * @Version: 1.0

 */

public class MinDistance {

    public int solution(String word1, String word2) {

        int w1 = word1.length(), w2 = word2.length();

        char w1s[] = word1.toCharArray(), w2s[] = word2.toCharArray();

        int[][] dpcost = new int[w1 + 1][w2 + 1];

        //初始化

        for (int i = 0; i <= w1; ++i) {

            dpcost[i][0] = i; //标识要把word1的i个字符化为0个，那就删i次

        }

        for (int j = 0; j <= w2; ++j) {

            dpcost[0][j] = j;

        }

        //这题动态规划了，比较复杂说实话

        //遍历

        for (int i = 1; i < dpcost.length; ++i) {

            for (int j = 1; j < dpcost[i].length; ++j) {

                //我们把动态规划递增的量设置为，word1前i个字符，转换为word2前j个字符需要的最小操作数

                //f(i,j) = f(i-1, j-1) 当word1[i] == word2[j]的时候，相等字符，那么当前字符就不需要花费操作次数

                if (w1s[i - 1] == w2s[j - 1]) {

                    dpcost[i][j] = dpcost[i - 1][j - 1];

                } else {

                    //当word1[i] != word2[j]的时候 分三种情况平衡

                    //1.进行插入操作, 那就是新增一个一样的字符和word2进行匹配，那就是word2的j位就直接新增进去，就不用比较了，我们取没有j号的次数

                    // f(i,j) = f(i, j-1) + 1;

                    int insert = dpcost[i][j - 1];

                    //2.当进行删除操作，那就是把word1当前字符删除掉，当前位置相当于不比较

                    // f(i,j)=f(i-1,j) + 1;

                    int remove = dpcost[i - 1][j];

                    //3.当进行替换操作，那就是把当前字符完全替换，那么就是新增一个操作，其余和之前一样

                    // f(i,j)=f(i-1,j-1) + 1;

                    int replace = dpcost[i - 1][j - 1];

                    dpcost[i][j] = Math.min(insert, Math.min(remove, replace)) + 1;

                }

            }

        }

        return dpcost[w1][w2];

    }

}

package y2019.Algorithm.str.hard;

import java.util.HashMap;

import java.util.Map;

/**

 * @ProjectName: cutter-point

 * @Package: y2019.Algorithm.str.hard

 * @ClassName: MinWindow

 * @Author: xiaof

 * @Description: 76. Minimum Window Substring

 * Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

 *

 * Example:

 *

 * Input: S = "ADOBECODEBANC", T = "ABC"

 * Output: "BANC"

 * Note:

 *

 * If there is no such window in S that covers all characters in T, return the empty string "".

 * If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

 * @Date: 2019/8/7 15:15

 * @Version: 1.0

 */

public class MinWindow {

    public String solution(String s, String t) {

        if (s == null || t == null || s.length() < t.length() || s.length() == 0 || t.length() == 0) {

            return "";

        }

        //用索引，并且是单次循环

        int l = 0, r = 0, count = t.length(), minle = s.length(), minl = 0, minr = 0;

        Map<Character, Integer> map = new HashMap();

        boolean pipeiok = false;

        //第一次循环，初始化map

        for (int i = 0; i < t.length(); ++i) {

            map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);

        }

        //循环遍历字符串

        while (r < s.length()) {

            //计算是否存在所有字符的子串

            char curc = s.charAt(r);

            if (map.containsKey(curc)) {

                //如果包含

                map.put(curc, map.get(curc) - 1);

                if (map.get(curc) >= 0) {

                    //如果有效匹配

                    --count;

                }

            }

            //如果全部匹配完成,存在单字符匹配

            while (count == 0 && l <= r) {

                pipeiok = true;

                int curlen = r - l + 1;

                if (curlen <= minle) {

                    //存在更小值

                    minl = l;

                    minr = r;

                    minle = curlen;

                }

                //更新最左边索引

                char leftc = s.charAt(l);

                if (map.containsKey(leftc)) {

                    //如果包含，那么就找到了最左边的第一个字符

                    //我们把这个位置的字符剔除掉，然后看是否可以找到更小的子串

                    map.put(leftc, map.get(leftc) + 1);

                    if (map.get(leftc) >= 1) {

                        //加一之后恢复到正常状态

                        count++;

                    }

                }

                //吧最左边右移一次

                l++;

            }

            r++; //往后遍历

        }

        return pipeiok == true ? s.substring(minl, minr + 1) : "";

    }

    public static void main(String[] args) {

        String s[] = {"ADOBECODEBANC", "ABC"};

        String s1[] = {"aa", "aa"};

        MinWindow fuc = new MinWindow();

        fuc.solution(s1[0], s1[1]);

    }

}