package personalwebsite.string;

/**
 * Created by liyou on 16/2/21. 拓扑结构相同子树问题
 * <p>
 * [LeetCode 572. 另一个树的子树](https://leetcode-cn.com/problems/subtree-of-another-tree/)
 * <p>
 * 对于两棵彼此独立的二叉树A和B，请编写一个高效算法，检查A中是否存在一棵子树与B树的拓扑结构完全相同。
 * 给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树。
 */
public class SubTreeDemo {

    // 递归法
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (t == null) return true;   // t 为 null 一定都是 true
        if (s == null) return false;  // 这里 t 一定不为 null, 只要 s 为 null，肯定是 false
        return isSubtree(s.left, t) || isSubtree(s.right, t) || isSameTree(s, t);
    }

    /**
     * 判断两棵树是否相同
     */
    public boolean isSameTree(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        if (s.val != t.val) return false;
        return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
    }

    // 最优解法为二叉树序列化 + KMP算法
    public boolean chkIdentical(TreeNode t1, TreeNode t2) {
        String t1Str = serialByPre(t1);
        String t2Str = serialByPre(t2);
        return getIndexOf(t1Str, t2Str) != -1;
    }

    private String serialByPre(TreeNode head) {
        if (head == null) {
            return "#!";
        }

        String res = head.val + "!";
        res += serialByPre(head.left);
        res += serialByPre(head.right);
        return res;
    }

    // KMP
    private int getIndexOf(String s, String m) {
        if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
            return -1;
        }
        char[] ss = s.toCharArray();
        char[] ms = m.toCharArray();

        int[] nextArr = getNextArray(ms);
        int index = 0;
        int mi = 0;
        while (index < ss.length && mi < ms.length) {
            if (ss[index] == ms[mi]) {
                index++;
                mi++;
            } else if (nextArr[mi] == -1) {
                index++;
            } else {
                mi = nextArr[mi];
            }
        }
        return mi == ms.length ? index - mi : -1;
    }

    private int[] getNextArray(char[] ms) {
        if (ms.length == 1) {
            return new int[]{-1};
        }
        int[] nextArr = new int[ms.length];
        nextArr[0] = -1;
        nextArr[1] = 0;
        int pos = 2;
        int cn = 0;
        while (pos < nextArr.length) {
            if (ms[pos - 1] == ms[cn]) {
                nextArr[pos++] = ++cn;
            } else if (cn > 0) {
                cn = nextArr[cn];
            } else {
                nextArr[pos++] = 0;
            }
        }
        return nextArr;
    }

    static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }
}

package personalwebsite.string;

/**
 * Created by liuzhif on 16/2/21.词语变形
 * <p>
 * [LeetCode 242. 有效的字母异位词](https://leetcode-cn.com/problems/valid-anagram/)
 * <p>
 * 对于两个字符串A和B，如果A和B中出现的字符种类相同且每种字符出现的次数相同，则A和B互为变形词，请设计一个高效算法，检查两给定串是否互为变形词。
 * 给定两个字符串A和B及他们的长度，请返回一个bool值，代表他们是否互为变形词。
 * 测试样例：
 * "abc",3,"bca",3
 * 返回：true
 */
public class WordTransformDemo {

    public static void main(String[] args) {
        WordTransformDemo demo = new WordTransformDemo();
        String a = "ac";
        String b = "bb";
        System.out.println(demo.isAnagram(a, b));
    }

    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;

        int[] array = new int[26];
        for (int i = 0; i < s.length(); i++) {
            array[s.charAt(i) - 'a']++;
            array[t.charAt(i) - 'a']--;
        }

        for (int j : array) {
            if (j != 0) return false;
        }

        return true;
    }

}

package personalwebsite.string;

/**
 * Created by LeeeYou on 2016/3/13. 两串旋转练习题
 * <p>
 * [LeetCode 796. 旋转字符串](https://leetcode-cn.com/problems/rotate-string/)
 * <p>
 * 如果对于一个字符串A，将A的前面任意一部分挪到后边去形成的字符串称为A的旋转词。比如A="12345",A的旋转词有"12345","23451","34512","45123"和"51234"。对于两个字符串A和B，请判断A和B是否互为旋转词。
 * 给定两个字符串A和B及他们的长度lena，lenb，请返回一个bool值，代表他们是否互为旋转词。
 * 测试样例：
 * "cdab",4,"abcd",4
 * 返回：true
 */
public class RotationStrDemo {

    public static void main(String[] args) {
        RotationStrDemo demo = new RotationStrDemo();
        System.out.println(chkRotation("love", 5, "elo", 5));
        System.out.println(demo.rotateString("love", "elo"));
    }

    public static boolean chkRotation(String str1, int n, String str2, int m) {
        if (n != m) return false;
        String a = str1 + str1;
        return getIndexOf(a, str2) != -1;
    }

    // KMP Algorithm
    public static int getIndexOf(String s, String m) {
        if (s.length() < m.length()) {
            return -1;
        }
        char[] ss = s.toCharArray();
        char[] ms = m.toCharArray();
        int si = 0;
        int mi = 0;
        int[] next = getNextArray(ms);
        while (si < ss.length && mi < ms.length) {
            if (ss[si] == ms[mi]) {
                si++;
                mi++;
            } else if (next[mi] == -1) {
                si++;
            } else {
                mi = next[mi];
            }
        }
        return mi == ms.length ? si - mi : -1;
    }

    public static int[] getNextArray(char[] ms) {
        if (ms.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[ms.length];
        next[0] = -1;
        next[1] = 0;
        int pos = 2;
        int cn = 0;
        while (pos < next.length) {
            if (ms[pos - 1] == ms[cn]) {
                next[pos++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[pos++] = 0;
            }
        }
        return next;
    }

    public boolean rotateString(String s, String goal) {
        return s.length() == goal.length() && (s + s).contains(goal);
    }
}

package personalwebsite.string;

import java.util.*;

/**
 * Created by LeeeYou on 2016/3/13. 句子的逆序练习题
 * <p>
 * [LeetCode 151. 翻转字符串里的单词](https://leetcode-cn.com/problems/reverse-words-in-a-string/)
 * <p>
 * 对于一个字符串，请设计一个算法，只在字符串的单词间做逆序调整，也就是说，字符串由一些由空格分隔的部分组成，你需要将这些部分逆序。
 * 给定一个原字符串A和他的长度，请返回逆序后的字符串。
 * 测试样例：
 * "dog loves pig",13
 * 返回："pig loves dog"
 */
public class ReverseDemo {

    public static void main(String[] args) {
        ReverseDemo demo = new ReverseDemo();

        String str1 = "dog loves pig";
        String str2 = "I'm a pig.";
        String str3 = " a good   example ";

        System.out.println(demo.reverseWords(str1));
        System.out.println(demo.reverseWords(str2));
        System.out.println(demo.reverseWords(str3));

        System.out.println();
        System.out.println(demo.reverseWords2(str1));
        System.out.println(demo.reverseWords2(str2));
        System.out.println(demo.reverseWords2(str3));

        System.out.println();
        System.out.println(demo.reverseWords3(str1));
        System.out.println(demo.reverseWords3(str2));
        System.out.println(demo.reverseWords3(str3));
    }

    // 双端队列法
    public String reverseWords3(String s) {
        int left = 0, right = s.length() - 1;
        while (left <= right && s.charAt(left) == ' ') ++left; // 去掉字符串开头的空白字符
        while (left <= right && s.charAt(right) == ' ') --right;  // 去掉字符串末尾的空白字符

        Deque<String> d = new ArrayDeque<>();
        StringBuilder word = new StringBuilder();

        while (left <= right) {
            char c = s.charAt(left);
            if ((word.length() != 0) && (c == ' ')) {
                // 将单词 push 到队列的头部
                d.offerFirst(word.toString());
                word.setLength(0);
            } else if (c != ' ') {
                word.append(c);
            }
            ++left;
        }
        d.offerFirst(word.toString());
        return String.join(" ", d);
    }

    // 系统api
    public String reverseWords2(String s) {
        if (s.isEmpty()) return null;
        List<String> list = Arrays.asList(s.split("\\s+"));
        Collections.reverse(list);
        return String.join(" ", list);
    }

    // 两次翻转法
    public String reverseWords(String s) {
        if (s.isEmpty()) return null;
        String[] strArray = reverse(s).split("\\s+"); // 按空格切割字符串
        String[] result = new String[strArray.length];
        for (int i = 0; i < strArray.length; i++) {
            result[i] = reverse(strArray[i]);
        }
        return String.join(" ", result);
    }

    public String reverse(String str) {
        int len = str.length();
        char[] chars = str.toCharArray();
        int i = 0;
        while (i < len / 2) {
            swap(chars, i, len - i - 1);
            ++i;
        }
        return new String(chars);
    }

    public void swap(char[] chars, int i, int j) {
        chars[i] = (char) (chars[i] ^ chars[j]);
        chars[j] = (char) (chars[i] ^ chars[j]);
        chars[i] = (char) (chars[i] ^ chars[j]);
    }
}

public static String stringTranslation(String A, int n, int len) {
    if (n == 1)
        return A;

    if (len <= 0 || len > n - 1)
        return A;

    char[] chars = A.toCharArray();

    reverse(chars, 0, len - 1);
    reverse(chars, len, n - 1);
    reverse(chars, 0, n - 1);

    return String.valueOf(chars);
}

public static void reverse(char[] chas, int start, int end) {
    char tmp;
    while (start < end) {
        tmp = chas[start];
        chas[start] = chas[end];
        chas[end] = tmp;
        start++;
        end--;
    }
}

public static class MyComparator implements Comparator<String> {
    @Override
    public int compare(String s1, String s2) {
        return (s1 + s2).compareTo(s2 + s1);
    }
}

public static String findSmallest(String[] strs, int n) {
    if (strs == null || strs.length <= 0)
        return null;

    Arrays.sort(strs, new MyComparator());
    StringBuilder sb = new StringBuilder();
    for (String str : strs) {
        sb.append(str);
    }

    return sb.toString();
}

package personalwebsite.string;

/**
 * Created by LeeeYou on 2016/3/14. 空格替换练习题
 * <p>
 * [LeetCode 剑指 Offer 05. 替换空格](https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/)
 * <p>
 * 请编写一个方法，将字符串中的空格全部替换为“%20”。假定该字符串有足够的空间存放新增的字符，并且知道字符串的真实长度(小于等于1000)，同时保证字符串由大小写的英文字母组成。
 * 给定一个string iniString 为原始的串，以及串的长度 int len, 返回替换后的string。
 * 测试样例：
 * "Mr John Smith”,13
 * 返回："Mr%20John%20Smith"
 * ”Hello  World”,12
 * 返回：”Hello%20%20World”
 */
public class ReplaceDemo {

    public static void main(String[] args) {
        ReplaceDemo demo = new ReplaceDemo();
        System.out.println(demo.replaceSpace("We are happy."));
        System.out.println(demo.replaceSpace2("We are happy."));
    }

    // 系统api
    public String replaceSpace(String s) {
        StringBuilder build = new StringBuilder();
        char[] chars = s.toCharArray();
        for (int i = chars.length - 1; i >= 0; i--) {
            if (chars[i] == ' ') {
                build.insert(0, "%20");
            } else {
                build.insert(0, chars[i]);
            }
        }
        return build.toString();
    }

    // 数组
    public String replaceSpace2(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') count++;
        }
        char[] cs = new char[s.length() + count * 2];
        int index = cs.length - 1;
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (c == ' ') {
                cs[index--] = '0';
                cs[index--] = '2';
                cs[index--] = '%';
            } else {
                cs[index--] = c;
            }
        }
        return new String(cs);
    }

}

package personalwebsite.string;

import java.util.*;

/**
 * Created by LeeeYou on 2016/3/14. 合法括号序列判断练习题
 * <p>
 * [LeetCode 20. 有效的括号](https://leetcode-cn.com/problems/valid-parentheses/)
 * <p>
 * 对于一个字符串，请设计一个算法，判断其是否为一个合法的括号串。
 * 给定一个字符串A和它的长度n，请返回一个bool值代表它是否为一个合法的括号串。
 * 测试样例：
 * "(()())",6
 * 返回：true
 * 测试样例：
 * "()a()()",7
 * 返回：false
 * 测试样例：
 * "()(()()",7
 * 返回：false
 */
public class BracketsDemo {

    public static void main(String[] args) {
        BracketsDemo demo = new BracketsDemo();

        String s1 = "()[]{}(({}))";
        String s2 = "(]";
        String s3 = "()";

        System.out.println();
        System.out.println(demo.isValid(s1));
        System.out.println(demo.isValid(s2));
        System.out.println(demo.isValid(s3));

        System.out.println();
        System.out.println(demo.isValid2(s1));
        System.out.println(demo.isValid2(s2));
        System.out.println(demo.isValid2(s3));

        System.out.println();
        System.out.println(demo.isValid3(s1));
        System.out.println(demo.isValid3(s2));
        System.out.println(demo.isValid3(s3));
    }

    // 栈 + 辅助HashMap
    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<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (pairs.containsKey(c)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(c)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }

    // 栈（不用辅助HashMap）
    public boolean isValid2(String s) {
        if (s.isEmpty()) return true;
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') stack.push(')');
            else if (c == '{') stack.push('}');
            else if (c == '[') stack.push(']');
            else if (stack.empty() || c != stack.pop()) return false;
        }
        return stack.empty();
    }

    // 替换法
    public boolean isValid3(String s) {
        while (s.contains("()") || s.contains("[]") || s.contains("{}")) {
            if (s.contains("()")) {
                s = s.replace("()", "");
            }
            if (s.contains("{}")) {
                s = s.replace("{}", "");
            }
            if (s.contains("[]")) {
                s = s.replace("[]", "");
            }
        }
        return s.length() == 0;
    }

}

package personalwebsite.string;

import java.util.HashSet;
import java.util.Set;

/**
 * Created by LeeeYou on 2016/3/14. 最长无重复字符子串练习题
 * <p>
 * [LeetCode 3. 无重复字符的最长子串](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/)
 * <p>
 * 对于一个字符串,请设计一个高效算法，找到字符串的最长无重复字符的子串长度。
 * 给定一个字符串A及它的长度n，请返回它的最长无重复字符子串长度。保证A中字符全部为小写英文字符，且长度小于等于500。
 * 测试样例：
 * "aabcb",5
 * 返回：3
 */
public class LongestSubstringDemo {

    public static void main(String[] args) {
        LongestSubstringDemo demo = new LongestSubstringDemo();

        String s1 = "abcabcbb";
        String s2 = "rfrxkfrb";

        System.out.println(demo.lengthOfLongestSubstring(s1));
        System.out.println(demo.lengthOfLongestSubstring(s2));
    }

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

}

package com.leeeyou.test.string;

import java.util.LinkedList;

/**
* Created by leeeyou on 2016/12/20.
*/
public class DeleteStr {
    public static void main(String[] args) {
        String sourceStr = "public class DeleteStr";
        String deleteStr = "cs";
        deleteStr(sourceStr, deleteStr);
    }

    private static void deleteStr(String sourceStr, String deleteStr) {
        if (sourceStr == null || deleteStr == null) {
            return;
        }

        int[] deleteCharAsciiArray = new int[256];
        char[] deleteCharArray = deleteStr.toCharArray();
        for (int i = 0; i < deleteCharArray.length; i++) {
            deleteCharAsciiArray[deleteCharArray[i]] = 1;
        }

        LinkedList<Character> linkedList = new LinkedList<>();
        char[] sourceCharArray = sourceStr.toCharArray();
        for (int i = 0; i < sourceCharArray.length; i++) {
            linkedList.add(sourceCharArray[i]);
        }

        for (int i = linkedList.size() - 1; i >= 0; i--) {
            if (deleteCharAsciiArray[linkedList.get(i)] == 1) {
                linkedList.remove(i);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < linkedList.size(); i++) {
            sb.append(linkedList.get(i));
        }
        System.out.print(sb.toString());
    }

}

package com.leeeyou.test.string;

/**
* Created by leeeyou on 2016/12/16.
*/
public class MoveStr {

    public static void main(String[] args) {
        String s = "*so*h*a*ppy**t*oday*";
        moveStr(s);
    }

    private static void moveStr(String s) {
        char[] chars = s.toCharArray();

        int slow = chars.length - 1;
        while ('*' != chars[slow]) {
            --slow;
        }

        for (int fast = slow - 1; fast >= 0; fast--) {
            if ('*' != chars[fast]) {
                chars[slow] = chars[fast];
                chars[fast] = '*';
                slow--;
            }
        }

        System.out.print(chars);
    }

}

package com.leeeyou.test.string;

/**
* Created by leeeyou on 2016/12/15.
*/
public class Permutation {
    public static void main(String[] args) {
        String s = "1234";
        char[] chars = s.toCharArray();
        permutation(chars, 0, chars.length - 1);
    }

    /**
     * 从集合依次选出每一个元素，作为排列的第一个元素，然后对剩余的元素进行全排列，如此递归处理.
     *
     * @param s    字符数组
     * @param from 起始位置
     * @param to   结束位置
     */
    public static void permutation(char[] s, int from, int to) {
        if (to <= 1) {
            return;
        }

        if (from == to) {
            System.out.println(s);
        } else {
            for (int i = from; i <= to; i++) {
                swap(s, i, from);
                permutation(s, from + 1, to);
                swap(s, from, i);
            }
        }
    }

    public static void swap(char[] s, int i, int j) {
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }
}