131. Split back substring

Given a string s, divide s into substrings so that each substring is a palindrome. Returns all possible split options for S.

A palindrome is a string that reads the same as it does backwards.

Example 1

Input: s = "aab" Output: [["a","a","b"],["aa","b"]]Copy the code

Example 2

Input: s = "a" output: [["a"]]Copy the code

solution

func partition(s string)[] []string {
    res:=[][]string{}
    dfs131(s,0.nil,&res)
    return res
}

func dfs131(s string,index int, temp []string, res *[][]string){
    if index==len(s){
        copyTemp:=make([]string.len(temp))
        copy(copyTemp,temp)
        *res=append(*res,copyTemp)
        return
    }
    fori:=index; i<len(s); i++{if checkStrCore(s,index,i){
            dfs131(s,i+1.append(temp,s[index:i+1]),res)
        }
    }
    return
}

func checkStrCore(s string,left int,right int)bool{
    for left<right{
        ifs[left]! =s[right]{return false
        }
        left++
        right--
    }
    return true
}
Copy the code

Their thinking

Copy the code

93. Restore the IP address

Given a numeric string representing an IP address, return all valid IP addresses that can be obtained from S. You can return the answers in any order.

A valid IP address consists of exactly four integers (each integer is between 0 and 255 and cannot contain a leading 0), separated by ‘.’.

For example, 0.1.2.201 and 192.168.1.1 are valid IP addresses, but 0.011.255.245, 192.168.1.312, and [email protected] are invalid IP addresses.

Example 1

Input: s = "25525511135" Output: ["255.255.11.135","255.255.111.35"]Copy the code

Example 2

Input: s = "0000" Output: ["0.0.0.0"]Copy the code

Example 3

Input: s = "1111" Output: ["1.1.1.1"]Copy the code

Example 4

Input: s = "010010" Output: ["0.10.0.10","0.100.1.0"]Copy the code

Example 5

Input: s = "101023" output: [" 1.0.10.23 ", "1.0.102.3", "10.1.0.23", "10.10.2.3", "101.0.2.3"]Copy the code

solution

func partition(s string)[] []string {
    res:=[][]string{}
    dfs131(s,0.nil,&res)
    return res
}

func dfs131(s string,index int, temp []string, res *[][]string){
    if index==len(s){
        copyTemp:=make([]string.len(temp))
        copy(copyTemp,temp)
        *res=append(*res,copyTemp)
        return
    }
    fori:=index; i<len(s); i++{if checkStrCore(s,index,i){
            dfs131(s,i+1.append(temp,s[index:i+1]),res)
        }
    }
    return
}

func checkStrCore(s string,left int,right int)bool{
    for left<right{
        ifs[left]! =s[right]{return false
        }
        left++
        right--
    }
    return true
}
Copy the code

Their thinking

Copy the code