# DFS on String

#### [680. Split String](https://www.lintcode.com/problem/split-string/description) (Lintcode)

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

```java
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](https://leetcode.com/problems/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))

```java
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](https://leetcode.com/problems/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.

```java
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](https://www.1point3acres.com/bbs/thread-671009-1-1.html)

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

```java
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。用递归很好解。

```java
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](https://leetcode.com/problems/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.

```java
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;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://howardyangemail.gitbook.io/decode-leetcode/dfs/dfs-on-string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.