C++ One-Pass Solution


  • 0

    C++ Accepted One-Pass Solution:

    class Solution {
    public:
        int lengthLongestPath(string input) {
            size_t maxFilePathLength = 0;
            vector<size_t> lengthStack;
            
            for (size_t idx = 0; idx < input.size(); ++idx) {
                // for a new segment
                
                // count the number of tabs
                size_t tabNum = 0;
                for (;(idx < input.size()) && (input[idx] == '\t'); ++idx) {
                    ++tabNum;
                }
                size_t baseValue = 0;
                if (tabNum != 0) {
                    baseValue = lengthStack[tabNum-1];
                }
                
                // count current segment size and determine whether it is a file.
                bool isFile = false;
                size_t segmentLength = 0;
                for (; (idx < input.size()) && (input[idx] != '\n'); ++idx) {
                    ++segmentLength;
                    if (input[idx] == '.') {
                        isFile = true;
                    }
                }
                
                size_t newLength = baseValue + segmentLength;
                if (isFile) {
                    if (maxFilePathLength < newLength) {
                        maxFilePathLength = newLength;
                    }
                }
                else { // is directory
                    ++newLength; // the slash
                    if (lengthStack.size() == tabNum) {
                        lengthStack.push_back(newLength);
                    }
                    else {
                        lengthStack[tabNum] = newLength;
                    }
                }
            }
            
            return static_cast<int>(maxFilePathLength);
        }
    };

  • 0

    yet another one-pass solution

    class Solution {
    public:
        int lengthLongestPath(string input) {
            size_t longestFilepathLength = 0;
            vector<size_t> segmentLengths;
            
            SegmentParameters param;
            for (char c : input) {
                if (c == '\n') {
                    update(longestFilepathLength, segmentLengths, param);
                    param = SegmentParameters(); // reset
                }
                else {
                    param.update(c);
                }
            }
            update(longestFilepathLength, segmentLengths, param);
            return static_cast<int>(longestFilepathLength);
        }
    private:
    
        struct SegmentParameters {
            bool isFile;
            size_t segmentLength;
            size_t tabNumber;
            SegmentParameters() : isFile(false), segmentLength(0), tabNumber(0) {}
            void update(char c) {
                if (c == '\t') {
                    ++tabNumber;
                }
                else {
                    ++segmentLength;
                    if (c == '.') {
                        isFile = true;
                    }
                }
            }
        };
        
        void update(size_t & longestFilepathLength, vector<size_t> & segmentLengths, const SegmentParameters & param) {
            size_t newLength = param.segmentLength;
            if (param.tabNumber > 0) {
                newLength += segmentLengths[param.tabNumber - 1];
            }
            if (param.isFile) {
                if (longestFilepathLength < newLength) {
                    longestFilepathLength = newLength;
                }
            }
            else { // is dictionary
                ++newLength; // the slash
                if (segmentLengths.size() == param.tabNumber) {
                    segmentLengths.push_back(newLength);
                }
                else {
                    segmentLengths[param.tabNumber] = newLength;
                }
            }
        }
    };

Log in to reply
 

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