DFS on String

680. Split String (Lintcode)

Split a string into substrings with size of 1 and 2. Use an index pointer to track the start point.

public List<List<String>> splitString(String s) {
    List<List<String>> res = new ArrayList<>();
    if (s == null || s.isEmpty()) {
        return res;
    }
    dfs(s, 0, res, new ArrayList<>());
    return res;
}

private void dfs(String s, int index, List<List<String>> res, List<String> curt) {
    if (index == s.length()) {
        res.add(new ArrayList<>(curt));
        return;
    }
    for (int i = index + 1; i <= index + 2 && i <= s.length(); i++) {
        curt.add(s.substring(index, i));
        dfs(s, i, res, curt);
        curt.remove(curt.size() - 1);
    }
}

131. Palindrome Partitioning

Backtracking to cut String s into a sub piece which is palindrome. Use a separate function to detect if the string is a palindrome. Use index to mark the current position and when it equals to the original s length, return.

Time complexity: O(n*(2^n))

• For a string with length n, there will be (n - 1) intervals between chars.

• For every interval, we can cut it or not cut it, so there will be 2^(n - 1) ways to partition the string.

• For every partition way, we need to check if it is palindrome, which is O(n). So the time complexity is O(n*(2^n))

int sLen;
public List<List<String>> partition(String s) {
    sLen = s.length();
    List<List<String>> res = new ArrayList<>();
    dfs(s, 0, new ArrayList<>(), res);
    return res;
}

private void dfs(String s, int index, List<String> curt, List<List<String>> res) {
    if (index == sLen) {
        res.add(new ArrayList<>(curt));
        return;
    }
    for (int i = 1; i <= s.length(); i++) {
        String sub = s.substring(0, i);
        if (isPalindrome(sub)) {
            curt.add(sub);
            dfs(s.substring(i, s.length()), index + sub.length(), curt, res);
            curt.remove(curt.size() - 1);
        }
    }
}

private boolean isPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i <= j) {
        if (s.charAt(i) != s.charAt(j)) {
            return false;
        }
        i++;
        j--;
    }
    return true;
}

132. Palindrome Partitioning II

Same 131, calculate a min on each level and return an overall min value. Return 0 when index reach length of original s. Also add memo.

int sLen;
public int minCut(String s) {
    sLen = s.length();
    return dfs(s, 0, new HashMap<>()) - 1;
}

private int dfs(String s, int index, Map<String, Integer> memo) {
    if (memo.containsKey(s)) {
        return memo.get(s);
    }
    if (index == sLen) {
        return 0;
    }
    int min = Integer.MAX_VALUE;
    for (int i = 1; i <= s.length(); i++) {
        String sub = s.substring(0, i);
        if (isPalindrome(sub)) {
            min = Math.min(min, dfs(s.substring(i, s.length()), index + sub.length(), memo) + 1);
        }
    }
    memo.put(s, min);
    return min;
}

private boolean isPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i <= j) {
        if (s.charAt(i) != s.charAt(j)) {
            return false;
        }
        i++;
        j--;
    }
    return true;
}

Find target string from a text

给一个目标字符串，从一个段text里面找到，并且返回index。

public static int findIndex(String text, String s) {
    for (int i = 0; i < text.length(); i++) {
        if (text.substring(i, i + s.length()).equals(s)) {
            return i;
        }
    }
    return -1;
}

Followup: 目标字符串可以允许通配符*，代表0或者多个任意字符。比如"*A", 从文档“CDFGAGB”，返回0。比如"A**B"，返回4。用递归很好解。

int tStart = 0;
public int findIndex2(String text, String s) {
    int startIndex = 0;
    while (startIndex < text.length() && s.charAt(startIndex) == '*') {
        startIndex++;
    }
    boolean res = dfs(text, 0, s, startIndex);
    if (!res) {
        return -1;
    }
    if (startIndex != 0) {
        return 0;
    }
    return tStart;
}

private boolean dfs(String t, int tIndex, String s, int sIndex) {
    if (sIndex == s.length()) {
        return tIndex <= t.length();
    }
    if (tIndex >= t.length()) {
        return false;
    }
    if (s.charAt(sIndex) == '*'
        && (dfs(t, tIndex + 1, s, sIndex) || dfs(t, tIndex + 1, s,
        sIndex + 1) || dfs(t, tIndex, s, sIndex + 1))) {
        return true;
    } else if (s.charAt(sIndex) == t.charAt(tIndex)) {
        if (sIndex == 0) {
            tStart = tIndex;
        }
        if (dfs(t, tIndex + 1, s, sIndex + 1)) {
            return true;
        }
    } else if (dfs(t, tIndex + 1, s, sIndex)) {
        return true;
    }
    return false;
}

471. Encode String with Shortest Length

DFS + Memo. DFS breakdown the string into different patterns determine if the string is constructed by the pattern ONLY. If the encoded candidate is shorter than the res, it is a better solution. Also break down the string into two parts and get the candidate from combining the left result and right result.

Map<String, String> map = new HashMap<>();
public String encode(String s) {
    if (s == null || s.length() == 0) return "";
    if (s.length() <= 4) return s;
    if (map.containsKey(s)) return map.get(s);
    String res = s;
    for (int k = s.length() / 2; k < s.length(); k++) {
        String pattern = s.substring(k);
        int count = countPattern(s, pattern);
        if (count == -1) continue;
        String candidate = String.valueOf(count) + "[" + encode(pattern) + "]";
        if (candidate.length() < res.length()) res = candidate;
    }
    
    for (int i = 1; i < s.length(); i++) {
        String left = s.substring(0, i), right = s.substring(i);
        String candidate = encode(left) + encode(right);
        if (candidate.length() < res.length()) res = candidate;
    }
    map.put(s, res);
    return res;
}

private int countPattern(String s, String p) {
    int count = 0, i = 0;
    while (i < s.length()) {
        if (s.substring(i).startsWith(p)) {
            count++;
            i += p.length();
        } else {
            return -1;
        }
    }
    return count * p.length() == s.length() ? count : -1;
}