O(n) C soln recursive


  • 0
    1
    int numSubDirs(char *ip, int ipLen, int *cOff, int *count) {
      int i=*cOff, subDirs=0;
      if(!ip) return -1;
      while(i<ipLen) {
        if(ip[i] == '\t') {
          *count =0;
          subDirs +=1;
          i+=1;
        }
        else
          break;
      }
      *cOff = i;
      return subDirs;
    }
    
    int longestLengthPath_int(char *ip, int ipLen, int *cOff,
                                              int *res,  int dirDpth, 
                                              int pathLen, int *count) {
      int currLen = pathLen, nxtDirDpth = dirDpth;
      while(*cOff < ipLen)  {
        if(ip[*cOff] == '\n') {
          *cOff+=1;
          *count=0;
          nxtDirDpth = numSubDirs(ip, ipLen, cOff, count);
          if (nxtDirDpth > dirDpth) 
              nxtDirDpth = longestLengthPath_int(ip, ipLen, cOff,
                      res, nxtDirDpth, currLen+1, count);
          if (nxtDirDpth == dirDpth) currLen = pathLen;
          if (nxtDirDpth < dirDpth)  return nxtDirDpth;
        }
        if(ip[*cOff] == '.') *count =1;
        currLen+=1;
        *cOff+=1;
    
        if ((*res < currLen) && *count)
          *res = currLen;
      }
      return nxtDirDpth;
    }
    
    int lengthLongestPath(char *input) {
      int iLen = strlen(input), ipIdx=0, res = 0, count=0;
      int nxtDepth=0;
    
      if(!input) return 0;
    
      longestLengthPath_int(input, iLen, &ipIdx, &res,
                            0, 0, &count);
      return res;
    }

  • 0
    V
    This post is deleted!

  • 0
    V
    This post is deleted!

  • 0
    1

    I think my solution is O(n) runtime. The recursion depth can be O(n) at the max. You can track the offset that is used to traverse through the input string. There is only one copy of it and its passed in as reference to other APIs.


Log in to reply
 

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