[演算法題目] Valid IP Addresses

本題資訊

難度：medium
使用語言：C++
相關概念：Strings

題目敘述

You’re given a string of length 12 or smaller, containing only digits. Write a function that returns all the possible IP addresses that can be created by inserting three .s in the string. An IP address is a sequence of four positive integers that are separated by .s, where each individual integer is within the range 0 – 255 , inclusive.

Input: 1921680
Output:

[
  "1.9.216.80",
  "1.92.16.80",
  "1.92.168.0",
  "19.2.16.80",
  "19.2.168.0",
  "19.21.6.80",
  "19.21.68.0",
  "19.216.8.0",
  "192.1.6.80",
  "192.1.68.0",
  "192.16.8.0"
]

這題的目的是依照給出的 input（只有小於 12 位數的數字），輸出所有合法的 IP。另外我只擷取了部分的題目，忽略的部分是在講合法的 IP 長相，大致上是 0 不能當一個區塊的開頭（除非只有一個數字），一個區塊最多三個數字，以及一個區塊的範圍只有 0-255。

Idea

這題理解上不會很困難，但實作上略為複雜。

因為整個過程分析下來會不斷遞迴，我希望能利用另外一個函式處理和判別目前字串。這個函式的 input 有 str、result、curr、index 以及 count。

str：題目給的字串。
result：最後要輸出的結果（一整排合法的 IP）。
curr：目前處理中的 IP 字串，初始值為空字串。
index ：目前處理到的 Index，初始值為 0。
count：計數器，初始值為 4。

原本是想用分割字串的方式再丟判斷，不過發現若直接合法的數字堆疊 數字.，等於直接 append 字串的方式或許會容易一些。而不合法的數字就會直接進行下一個迴圈，根本不會被輸出。

void check(string str, vector<string> &result, string curr, int index, int count){
  //check index and count
  if (count <= 0 || str.size() <= index){
    if (index == str.size() && count == 0){
      curr.pop_back(); //去除最後多的 '.'
      result.push_back(curr);
      return;
    }
    return;
  }
  
  //判斷每個區塊內共1~3個數字
  for (int i = 1; i <= 3; i++){
    string sub = str.substr(index, i);
    if (1 < sub.size() && sub[0] == '0')
      continue;
    if (0 <= stoi(sub) && stoi(sub) <= 255){
      check(str, result, curr + sub + ".", index + i, count - 1);
    }
  }
}

處理上就簡單多了：

vector<string> validIPAddresses(string str) {
  vector<string> result;
  check(str, result, "", 0, 4);
  return result;
}

時間複雜度：\(O(1)\)
空間複雜度：\(O(1)\)