0ms C example with recursive and link list


  • 1
    P

    I cannot find a C example in this discussion so I want to share my idea.
    Basically I solve it by recursive function and self designed link list.

    /*
    * Node structure:
    *    cnt               - The repeat count for current node.
    *    len               - The string length in current node.
    *                          (From pCurStr or the sum of all child node)
    *    pCurStr       - The sub-string content. (note)
    *    pChildNxt    - Link to child nodes.
    *    pSubStrNxt - Link to next nodes.
    * Note:
    *    For a set of characters, it will create a node to save the content.
    *    For a set of characters in "[]", it will create a child node.
    *    Ex. 
    *        char *s = "efg13[ad23[tyu]abg]";
    *        it contains:
    *        node(efg)  -> child(repeat 13)
    *                              => node(ad) -> child(repeat 23) -> node(abg)
    *                                                       => node(tyu)
    *                                                
    */
    struct StringNode {
    	int cnt;
    	int len;
    	char *pCurStr;
    	struct StringNode *pChildNxt;
    	struct StringNode *pSubStrNxt;
    };
    /*
    * This func is to count the sub-string length.
    * ex.
    *      char *s = "ef2[abc]"
    *      sub-string is "ef"
    *      CntToSubStrEnd(s) will return 2
    */
    int CntToSubStrEnd(char *s) {
    	int RetVal = 0;
    	while (*s && ((*s < '0') || (*s > '9')) && (*s != '[') && (*s != ']')) {
    		s++;
    		RetVal++;
    	}
    	return RetVal;
    }
    /*
    * This func will parse the number
    * ex.
    *      char *s = "12[abc]"
    *      GetNum(s, &Num) will return 2 and Num will equals to 12
    */
    int GetNum(char *s, int *pNum) {
    	int RetVal = 0;
    	*pNum = 0;
    	while (*s && (*s >= '0') && (*s <= '9')) {
    		*pNum = *pNum * 10;
    		*pNum = *pNum + *s - '0';
    		RetVal++;
    		s++;
    	}
    	return RetVal;
    }
    /*
    * This func will count the length between '[' and ']'
    * ex.
    *      char *s = "12[abc]"
    *      CntSymboInterval(s) will return 3
    */
    int CntSymboInterval(char *s) {
    	int Flag = 1;
    	int RetVal = 0;
    	//Move to first symbo
    	while (*s != '[') s++;
    	s++;
    	while (*s && Flag) {
    		if (*s == '[')
    			Flag++;
    		else if (*s == ']')
    			Flag--;
    		RetVal++;
    		s++;
    	}
    	RetVal--;
    	return RetVal;
    }
    /*
    * Main recursive function to process string
    */
    int StringProc(char *s, int len, struct StringNode **pNode) {
    	int i;
    	int CurStrLen = 0;
    	int AccumStrLen = 0;
    	int ProcLen = 0;
    	struct StringNode *pCurNode;
    	pCurNode = (struct StringNode *)calloc(1, sizeof(struct StringNode));
    	*pNode = pCurNode;
    	while (ProcLen < len) {
    		if ((*s >= '0') && (*s <= '9')) {
    			CurStrLen = GetNum(s, &(pCurNode->cnt));
    			s += CurStrLen;
    			ProcLen += CurStrLen;
    			CurStrLen = CntSymboInterval(s);
    			pCurNode->len = StringProc(s + 1
    				, CurStrLen
    				, &(pCurNode->pChildNxt));
    			s = s + 2 + CurStrLen;
    			AccumStrLen += ((pCurNode->len) * (pCurNode->cnt));
    			ProcLen += (CurStrLen + 2);
    		}
    		else {
    			CurStrLen = CntToSubStrEnd(s);
    			pCurNode->cnt = 1;
    			pCurNode->len = CurStrLen;
    			pCurNode->pCurStr = (char *)malloc((CurStrLen + 1) * sizeof(char));
    			for (i = 0; i < CurStrLen; i++) {
    				*(pCurNode->pCurStr + i) = *(s + i);
    			}
    			*(pCurNode->pCurStr + i) = 0;
    			s += CurStrLen;
    			AccumStrLen += CurStrLen;
    			ProcLen += CurStrLen;
    		}
    		if (ProcLen < len) {
    			pCurNode->pSubStrNxt
    				= (struct StringNode *)calloc(1, sizeof(struct StringNode));
    			pCurNode = pCurNode->pSubStrNxt;
    		}
    	}
    	return AccumStrLen;
    }
    /*
    * Main recursive function to fill in output string
    */
    void FillInStr(struct StringNode *pHead, char *pDst) {
    	int i, j;
    	struct StringNode *pSubN;
    	while (pHead) {
    		for (i = 0; i < pHead->cnt; i++) {
    			if (pHead->pCurStr) {
    				for (j = 0; j < pHead->len; j++) {
    					*(pDst + j) = *(pHead->pCurStr + j);
    				}
    				pDst = pDst + pHead->len;
    			}
    			else {
    				pSubN = pHead->pChildNxt;
    				FillInStr(pSubN, pDst);
    				pDst = pDst + pHead->len;
    			}
    		}
    		pHead = pHead->pSubStrNxt;
    	}
    }
    
    char* decodeString(char* s) {
    	char *pRet;
    	int len = strlen(s);
    	struct StringNode *pHead = NULL;
    	if (len == 0) {
    	    pRet = (char *)malloc(sizeof(char));
    	    *pRet = 0;
    	    return pRet;	    
    	}
    	len = StringProc(s, len, &pHead);
    	pRet = (char *)malloc((len + 1) * sizeof(char));
    	FillInStr(pHead, pRet);
    	*(pRet + len) = 0;
    	return pRet;
    }
    

Log in to reply
 

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