题解 | #数字字符串转化成IP地址#

package main


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param s string字符串
 * @return string字符串一维数组
 */
func restoreIpAddresses(s string) []string {
	// write code here
	var result []string
	var path []string
	backtrack(s, 0, path, &result)
	return result
}

func backtrack(s string, start int, path []string, result *[]string) {
	if len(path) == 4 {
		if start == len(s) {
			*result = append(*result, path[0]+"."+path[1]+"."+path[2]+"."+path[3])
		}
		return
	}

	for length := 1; length <= 3; length++ {
		if start+length > len(s) { // Prevent out of bounds
			break
		}
		temp := s[start : start+length]
		if (temp[0] == '0' && length > 1) || (length == 3 && temp > "255") { // Check if valid segment
			break
		}
		path = append(path, temp)                // Choose
		backtrack(s, start+length, path, result) // Explore
		path = path[:len(path)-1]                // Unchoose (backtrack)
	}
}