未分類

Restore IP Addresses

Backtracking, Go, LeetCode, String

Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:

1
2
3
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
提示 解題應用
Backtracking Recursive
String 規律觀查

Default:

1
2
3
func restoreIpAddresses(s string) []string {
}

解答思路:

要將一串數字轉為合法的IP位址，首先就要先知道合法IP位址的規則是什麼，最主要是要符合三樣條件:

  1. IP位址共包含四段，不能多也不能少
  2. 每一段的範圍介於0~255之間
  3. 超過2位數以上(包含)的第一個數不得為0，例如: 01, 023

在了解規則之後，便能透過遞回的方式排列組合出所有符合條件的結果，而要注意的一點是在遞回的過程中除了帶入現已組出的IP網段與剩餘尚未組合的數字至遞回函數之外，還要記得再多帶一個數字參數用以計算目前已組出的IP網段到第幾段，以利後續判斷時確保網段共包含四段，並且完全使用所給予數字字串的每個數字。

程式碼解說:

一開始便將初始值帶入遞回函數之中以組合出所有符合條件的結果，其中第一個參數為現已組出的IP網段字串，第二個則是數字參數用以計算目前已組出的IP網段字串到第幾段，最後才是剩餘尚未組合的數字

1
2
3
func restoreIpAddresses(s string) []string {
	return combine("", 1, s)
}

接著便開始處理遞回時要做的細節，在組合符合條件的合法IP之前，先判斷目前已組出的IP網段字串已經到第幾段，如果已經到了第5段表示前面的4段已經組合完畢，這時再判斷剩餘尚未組合的數字是否為空，如果是就回傳已組合完畢的合法IP，這邊要注意到回傳的合法IP不包含最後一個字元，因為後續在做組合時，每段後頭都會再放上”.”，所以到了第4段之後就要將”.”給除去，而如果還有剩餘尚未組合的數字，此時則回傳一個空的字串陣列即可

1
2
3
4
5
6
7
8
9
func combine(cur string, count int, s string) []string {
	if count > 4 {
		if s == "" {
			return []string{cur[:len(cur)-1]}
		}
		return []string{}
	}
	...
}

如果IP網段字串尚未組合完畢，繼續從剩餘尚未組合的數字字串一一取值，再以一變數來暫存這一段網段的數字字串，如果目前的網段數字字串長度大於1且第一個字元為”0”的話，此為不合法的IP地址直接結束迴圈，而如果上述綱段符合條件再將字串轉為數字檢查符圍是否介於0~255之間，如果超出符圍一樣也是不合法的IP地址直接結束迴圈，最後如果該網段條件皆符合，將現已組出的IP網段與該網段組合並再最後加上”.”，隨後將已組出的IP網段數+1連同剩餘尚未組合的數字字串再次帶入遞回之中，待回傳完整的IP位址才放入結果陣列之中，在剩餘尚未組合的數字字串完全取完結束迴圈之後，最後便向上回傳整個結果陣列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var subnet string
var ip []string
var result []string
for i, digit := range s {
	subnet += string(digit)
	if len(subnet) > 1 && subnet[0] == 48 {
		break
	}
	subInt, _ := strconv.Atoi(subnet)
	if subInt <= 255 {
		ip = combine(cur+subnet+".", count+1, s[i+1:])
		result = append(result, ip...)
	} else {
		break
	}
}
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func restoreIpAddresses(s string) []string {
	return combine("", 1, s)
}
func combine(cur string, count int, s string) []string {
	if count > 4 {
		if s == "" {
			return []string{cur[:len(cur)-1]}
		}
		return []string{}
	}
	var subnet string
	var ip []string
	var result []string
	for i, digit := range s {
		subnet += string(digit)
		if len(subnet) > 1 && subnet[0] == 48 {
			break
		}
		subInt, _ := strconv.Atoi(subnet)
		if subInt <= 255 {
			ip = combine(cur+subnet+".", count+1, s[i+1:])
			result = append(result, ip...)
		} else {
			break
		}
	}
	return result
}

總結:

要將一串數字轉為各種不同合法的IP位址陣列的話，只要能了解合法IP位址規則之後，便能透過遞回的方式排列組合出所有符合條件的結果，唯一要注意的是記得再多帶一個數字至遞回參數用以計算目前已組出的IP網段到第幾段，以利後續判斷時確保網段共包含四段，並且完全使用所給予數字字串的每個數字。

分享到