首页 > 试题广场 >

数字字符串转化成IP地址

[编程题]数字字符串转化成IP地址
  • 热度指数:67569 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
现在有一个只包含数字的字符串,将该字符串转化成IP地址的形式,返回所有可能的情况。
例如:
给出的字符串为"25525522135",
返回["255.255.22.135", "255.255.221.35"]. (顺序没有关系)

数据范围:字符串长度 0 \leq n \leq 12
要求:空间复杂度 ,时间复杂度

注意:ip地址是由四段数字组成的数字序列,格式如 "x.x.x.x",其中 x 的范围应当是 [0,255]。

示例1

输入

"25525522135"

输出

["255.255.22.135","255.255.221.35"]
示例2

输入

"1111"

输出

["1.1.1.1"]
示例3

输入

"000256"

输出

[]
int strsearch(char* s, char c) {
    int i;
    for(i=0;i<strlen(s);i++) {
        if(s[i]==c)
            return i;
    }
    return -1;
}
bool judgenum(char* s, int n) {
    int i,num=0;
    if(!n)
        return false;
    for(i=0;i<n;i++) {
        if((s[i]<'0')||(s[i]>'9'))
            return false;
        if((i==0)&&(s[i]=='0')&&(n!=1))
            return false;
        num *= 10;    
        num += s[i]-'0';
    }
    if(num>255)
        return false;
    return true;
}
bool solve(char* IP ) {
    int i;
    int Point_LOC=0;
    for(i=0;i<4;i++) {
        int NumLength = strsearch(IP+Point_LOC,'.');
        if(NumLength>0) {
            if(!judgenum(IP+Point_LOC,NumLength))
                return false;
            Point_LOC += NumLength+1;
        }
        else {
            if(!judgenum(IP+Point_LOC,strlen(IP)-Point_LOC))
                return false;
            Point_LOC += NumLength+1;
            break;
        }
    }
    return true;
}
char** restoreIpAddresses(char* s, int* returnSize ) {
    int i,j,k,m=0;
    char buf[12+4], **res;
    if(strlen(s)<4) {
        *returnSize = 0;
        return NULL;
    }
    res = (char**)malloc(100*sizeof(char*));
    for(i=0; i<strlen(s)-2; i++) {
        for(j=0; j<strlen(s)-1-i; j++) {
            for(k=0; k<strlen(s)-i-j; k++) {
                strncpy(buf, s, i);
                buf[i]='.';
                strncpy(buf+i+1, s+i, j);
                buf[i+1+j]='.';
                strncpy(buf+i+1+j+1, s+i+j, k);
                buf[i+1+j+1+k]='.';
                strcpy(buf+i+1+j+1+k+1, s+i+j+k);
                if(solve(buf)) {
                    res[m] = (char*)malloc(sizeof(buf));
                    strcpy(res[m++], buf);
                }
            }
        }
    }
    *returnSize = m;
    return res;
}

发表于 2024-03-24 16:09:59 回复(0)

问题信息

难度:
1条回答 35991浏览

热门推荐

通过挑战的用户

查看代码