找包含N个substring的最小string

给两个string，比如 lee和eel, 找到一个最短的string, 它的substring包含这两个stirng, 比如 leel.

找A与B的交集

// time O(m*n)
class Solution {
    public String findString(String s1, String s2) {
        if (s1.equals(s2)) {
            return s1;
        }

        // longer one is a, shorter one is b
        String a = s1.length() > s2.length() ? s1 : s2;
        String b = s1.length() > s2.length() ? s2 : s1;

        if (a.indexOf(b) != -1) {
            return a;
        }

        int indexA = -1;
        int indexB = -1;
        int substringLen = 0;
        boolean BFrontSame = true;

        // from b start same
        int start = a.length() - b.length();
        int j = 0;
        for (int i = start; i < a.length(); i++) { // index in a
            for (j = 0; j < a.length() - i; j++) {  // index in b
                if (a.charAt(i) != b.charAt(j)) {
                    break;
                }
            }

            if (j == a.length() - i) { // find common part
                indexA = i;
                indexB = j;
                substringLen = j;
                break;
            }
        }

        // from b end same
        start = b.length() - 1;
        j = 0;
        for (int i = start; i >= 0; i--) { // index in a
            for (j = b.length() - 1; j >= b.length() - i - 1; j--) {  // index in b
                if (a.charAt(i) != b.charAt(j)) {
                    break;
                }
            }

            if (j == b.length() - i - 2) { // find common part
                if (substringLen < b.length() - j - 1) {
                    BFrontSame = false;
                    indexA = i;
                    indexB = j;
                    substringLen = b.length() - i;
                }
                break;
            }
        }

        if (substringLen == 0) {
            return s1 + s2;
        }

        if (BFrontSame) {
            return a + b.substring(indexB);
        }

        return b + a.substring(indexA + 1);
    }
}

Follow-up :
给一堆string怎么办？

k-merge问题

class Solution {
    public String findAll(String[] strs) {
        if (strs == null || strs.length() == 0) {
            return "";
        }

        return mergeHelper(strs, 0, strs.length - 1);
    }

    private String mergeHelper(String[] strs, int s, int e) {
        if (s + 1 == e) {
            return findString(strs[s], strs[e]);
        }

        if (s == e) {
            return strs[s];
        }

        int mid = s + (e - s) / 2;
        String s1 = mergeHelper(strs, s, mid);
        String s2 = mergeHelper(strs, mid + 1, e);
        return findString(s1, s2);
    }

    private String findString(String s1, String s2) {
        if (s1.equals(s2)) {
            return s1;
        }

        // longer one is a, shorter one is b
        String a = s1.length() > s2.length() ? s1 : s2;
        String b = s1.length() > s2.length() ? s2 : s1;

        if (a.indexOf(b) != -1) {
            return a;
        }

        int indexA = -1;
        int indexB = -1;
        int substringLen = 0;
        boolean BFrontSame = true;

        // from b start same
        int start = a.length() - b.length();
        int j = 0;
        for (int i = start; i < a.length(); i++) { // index in a
            for (j = 0; j < a.length() - i; j++) {  // index in b
                if (a.charAt(i) != b.charAt(j)) {
                    break;
                }
            }

            if (j == a.length() - i) { // find common part
                indexA = i;
                indexB = j;
                substringLen = j;
                break;
            }
        }

        // from b end same
        start = b.length() - 1;
        j = 0;
        for (int i = start; i >= 0; i--) { // index in a
            for (j = b.length() - 1; j >= b.length() - i - 1; j--) {  // index in b
                if (a.charAt(i) != b.charAt(j)) {
                    break;
                }
            }

            if (j == b.length() - i - 2) { // find common part
                if (substringLen < b.length() - j - 1) {
                    BFrontSame = false;
                    indexA = i;
                    indexB = j;
                    substringLen = b.length() - i;
                }
                break;
            }
        }

        if (substringLen == 0) {
            return s1 + s2;
        }

        if (BFrontSame) {
            return a + b.substring(indexB);
        }

        return b + a.substring(indexA + 1);
    }
}