純數字字元串轉ip位址

leetcode 93. Restore IP Addresses

一、問題描述

        給定一個隻包含數字的字元串，通過傳回所有可能的有效IP位址組合來恢複它。

        【舉例】

        輸入: "25525511135"

        輸出: ["255.255.11.135", "255.255.111.35"]

二、解題思路

        從頭到尾周遊所有可能的ip組合，将組合的ip先暫存到中間數組中---使用深度優先，及時将不符合的組合剪枝，再将合法的ip組合放入最終結果數組。

三、算法代碼

/*******************************************************
Author:tmw
date:2018-5-14
********************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
參數：
*s    : 源數字字元串
*ip   ：存儲臨時轉的位址
start ：有效ip位址分4段，start為每一段的起始下标
step  ：記錄已分出的ip位址段數
**result ：轉換成有效ip位址的所有可能情況
**/

/**将ch字元串追加到str末尾**/
char* add_one_ch( char* str, char ch )
{
    int len = strlen(str);
    str[len] = ch;
    str[len+1] = '\0';
    return str;
}
int count = 0;/**記錄找到有效ip的個數**/
void Str_2_Ip_dfs( char* s, char* ip, int start, int step, char** result )
{
    /**當start下标到達s最後一個字元的下一位，說明此種情況下的有效ip位址轉換完畢**/
    if( start == strlen(s) && step == 4 )
    {
        ip[strlen(ip)-1] = '\0';
        strcpy(result[count],ip);
        count++;

        return;
    }

    /**剪枝語句**/
    /**目前組合情況如果導緻後面的元素偏多，則及時傳回**/
    if( strlen(s)-start > (4-step)*3 ) return;

    /**目前組合情況如果導緻後面的元素個數不足以最終轉換成xxx.xxx.xxx.xxx，則及時傳回**/
    if( strlen(s)-start < (4-step) )  return;

    int i;
    int sum = 0;
    /**ip位址最多是百位數字**/
    for( i=start; i<start+3; i++ )
    {
        sum = sum*10 + (s[i]-'0');

        /**對所有可能進行dfs**/
        if( sum <= 255 )
        {
            /**将目前可能的組合情況存入ip空間中**/
            add_one_ch(ip,s[i]);
            int mark_len = strlen(ip);/**記dfs前的狀态**/
            Str_2_Ip_dfs(s,add_one_ch(ip,'.'),i+1,step+1,result);
            ip[mark_len]='\0'; /**狀态恢複**/
        }

        /**ip位址字首不能為0,0可以單獨成一段，上一個if的前面則0就認為不能成一段**/
        if( sum == 0 ) break;
    }

}

/**
*s         ：源數字字元串
*returnSize：用于傳回找到的有效ip的個數
**/
char** restoreIpAddresses(char* s, int* returnSize)
{
    /**為臨時結果ip和最終結果result申請空間,給臨時存儲空間初始化**/
    char* ip = (char*)malloc(20*sizeof(char));
    memset(ip,0,strlen(ip));

    char** result = (char**)malloc(1000*sizeof(char*));
    int i;
    count = 0;

    for( i=0; i<1000; i++ )
        result[i] = (char*)malloc(20*sizeof(char));

    Str_2_Ip_dfs( s,ip,0,0,result );
    *returnSize = count;
    return result;
}
           

四、執行結果

leetcode accept

夢想還是要有的，萬一實作了呢~~~~ヾ(◍°∇°◍)ﾉﾞ~~~