C solution - time complexity O(n)


  • 1
    J
    /**
    * Return an array of size *returnSize.
    * Note: The returned array must be malloced, assume caller calls free().
    */
    
    #include <stdlib.h>
    #include <string.h>
    
    static char startArr[16] = {
    	/*  0, 1, 2, 3, 4, 5, 6,  7,  8,  9, 10, 11, 12 */
    		0, 0, 0, 0, 0, 1, 5, 15, 31, 50, 66, 76, 80, 81, 0, 0
    };
    
    static char patterns[81][4] = {
    	/* 4 - 1 */
    	{ 1, 1, 1, 1 },
    	/* 5 - 4 */
    	{ 1, 1, 1, 2 },
    	{ 1, 1, 2, 1 },
    	{ 1, 2, 1, 1 },
    	{ 2, 1, 1, 1 },
    	/* 6 - 10 */
    	{ 1, 1, 1, 3 },
    	{ 1, 1, 3, 1 },
    	{ 1, 3, 1, 1 },
    	{ 3, 1, 1, 1 },
    	{ 1, 1, 2, 2 },
    	{ 1, 2, 1, 2 },
    	{ 2, 1, 1, 2 },
    	{ 1, 2, 2, 1 },
    	{ 2, 1, 2, 1 },
    	{ 2, 2, 1, 1 },
    	/* 7 - 16 */
    	{ 1, 1, 2, 3 },
    	{ 1, 2, 1, 3 },
    	{ 2, 1, 1, 3 },
    	{ 1, 1, 3, 2 },
    	{ 1, 2, 3, 1 },
    	{ 2, 1, 3, 1 },
    	{ 1, 3, 1, 2 },
    	{ 1, 3, 2, 1 },
    	{ 2, 3, 1, 1 },
    	{ 3, 1, 1, 2 },
    	{ 3, 1, 2, 1 },
    	{ 3, 2, 1, 1 },
    	{ 1, 2, 2, 2 },
    	{ 2, 1, 2, 2 },
    	{ 2, 2, 1, 2 },
    	{ 2, 2, 2, 1 },
    	/* 8 - 19 */
    	{ 1, 1, 3, 3 },
    	{ 1, 3, 1, 3 },
    	{ 3, 1, 1, 3 },
    	{ 1, 3, 3, 1 },
    	{ 3, 1, 3, 1 },
    	{ 3, 3, 1, 1 },
    	{ 1, 2, 2, 3 },
    	{ 2, 1, 2, 3 },
    	{ 2, 2, 1, 3 },
    	{ 1, 2, 3, 2 },
    	{ 2, 1, 3, 2 },
    	{ 2, 2, 3, 1 },
    	{ 1, 3, 2, 2 },
    	{ 2, 3, 1, 2 },
    	{ 2, 3, 2, 1 },
    	{ 3, 1, 2, 2 },
    	{ 3, 2, 1, 2 },
    	{ 3, 2, 2, 1 },
    	{ 2, 2, 2, 2 },
    	/* 9 - 16 */
    	{ 1, 2, 3, 3 },
    	{ 2, 1, 3, 3 },
    	{ 1, 3, 2, 3 },
    	{ 2, 3, 1, 3 },
    	{ 3, 1, 2, 3 },
    	{ 3, 2, 1, 3 },
    	{ 1, 3, 3, 2 },
    	{ 2, 3, 3, 1 },
    	{ 3, 1, 3, 2 },
    	{ 3, 2, 3, 1 },
    	{ 3, 3, 1, 2 },
    	{ 3, 3, 2, 1 },
    	{ 2, 2, 2, 3 },
    	{ 2, 2, 3, 2 },
    	{ 2, 3, 2, 2 },
    	{ 3, 2, 2, 2 },
    	/* 10 - 10 */
    	{ 1, 3, 3, 3 },
    	{ 3, 1, 3, 3 },
    	{ 3, 3, 1, 3 },
    	{ 3, 3, 3, 1 },
    	{ 2, 2, 3, 3 },
    	{ 2, 3, 2, 3 },
    	{ 3, 2, 2, 3 },
    	{ 2, 3, 3, 2 },
    	{ 3, 2, 3, 2 },
    	{ 3, 3, 2, 2 },
    	/* 11 - 4 */
    	{ 2, 3, 3, 3 },
    	{ 3, 2, 3, 3 },
    	{ 3, 3, 2, 3 },
    	{ 3, 3, 3, 2 },
    	/* 12 - 1 */
    	{ 3, 3, 3, 3 }
    };
    
    char * GenMatched(char * p, char * str, int len) {
    	char * result, * t = str;
    	int i, j;
    
    	result = malloc(len + 4);
    	i = 0;
    	for (j = 0; j < p[0]; ++j) {
    		result[i++] = str[j];
    	}
    	result[i++] = '.';
    	str += p[0];
    	for (j = 0; j < p[1]; ++j) {
    		result[i++] = str[j];
    	}
    	result[i++] = '.';
    	str += p[1];
    	for (j = 0; j < p[2]; ++j) {
    		result[i++] = str[j];
    	}
    	result[i++] = '.';
    	str += p[2];
    	for (j = 0; j < p[3]; ++j) {
    		result[i++] = str[j];
    	}
    	result[i] = 0;
    	return result;
    }
    
    int Check3Pattern(char * str) {
    	if (str[0] != '1' && str[0] != '2') {
    		return 0 != 0;
    	}
    	if (str[0] == '2') {
    		if (str[1] >= '6') {
    			return 0 != 0;
    		}
    		if (str[1] == '5' && str[2] >= '6') {
    			return 0 != 0;
    		}
    	}
    	return 0 == 0;
    }
    
    int CheckPattern(char * p, char * str) {
    	int i;
    
    	for (i = 0; i < 4; ++i) {
    		switch (p[i]) {
    		case 3:
    			if (!Check3Pattern(str)) {
    				return 0 != 0;
    			}
    			break;
    		case 2:
    			if (*str == '0') {
    				return 0 != 0;
    			}
    			break;
    		case 1:
    			break;
    		default:
    			return 0 != 0;
    		}
    		str += p[i];
    	}
    	return 0 == 0;
    }
    
    char** restoreIpAddresses(char* s, int* returnSize) {
    	char ** result;
    	size_t len;
    	int i, u, pos;
    
    	len = strlen(s);
    	if (len < 4 || len > 12) {
    		*returnSize = 0;
    		return NULL;
    	}
    	i = startArr[len];
    	u = startArr[len + 1];
    	result = malloc((u - i) * sizeof(char *));
    	for (pos = 0; i < u; ++i) {
    		if (CheckPattern(patterns[i], s)) {
    			result[pos++] = GenMatched(patterns[i], s, len);
    		}
    	}
    	if (pos == 0) {
    		free(result);
    		result = NULL;
    	}
    	*returnSize = pos;
    	return result;
    }

  • 0
    T

    Why are you saying this is O(n)? Your search is constrained to u-i iterations. Each iteration traverses len+len times at worst (CheckPattern + GenMatched). So the complexity is (u-i)*(len+len) which is worst when len==9: (66-50)*(9+9)=288 input accesses, so for any input it will run at most in 288 time, which is O(1).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.