Verbose C++ 3ms solution using automata


  • 0
    _

    class Solution {

    private:

    const int NONE = 0;
    const int NEWLINE = 1;
    const int NEWLINE_TAB = 2;
    const int NEWLINE_TAB_DIR = 3;
    const int NEWLINE_TAB_POINT = 4;
    const int NEWLINE_TAB_FILE = 5;
    const int ERROR = 6;
    int spaces = 0;
    

    public:

    int getNextInnerState(int state, int car) {
        int nextState = NONE;
        switch(car){
            case '\n':
                nextState = (state == NONE || state == NEWLINE_TAB_DIR || state == NEWLINE_TAB_POINT || state == NEWLINE_TAB_FILE) ? NEWLINE : ERROR;
                spaces = 0;
                break;
            case '\t':
                nextState = (state == NEWLINE || state == NEWLINE_TAB) ? NEWLINE_TAB : ERROR;
                break;
            case '.':
                if(state == NEWLINE_TAB_FILE || state == NONE) {
                    nextState = NEWLINE_TAB_FILE;
                } else if(state == NEWLINE_TAB || state == NEWLINE_TAB_DIR || state == NEWLINE_TAB_POINT) {
                    nextState = NEWLINE_TAB_POINT;
                } else {
                    nextState = ERROR;
                }
                break;
            default:
                if(car == ' ' && state == NEWLINE) {
                    spaces++;
                    if(spaces == 4) {
                        nextState = (state == NEWLINE || state == NEWLINE_TAB) ? NEWLINE_TAB : ERROR;
                    } else {
                        nextState = state;
                    }    
                } else {
                    if(state == NONE || state == NEWLINE_TAB || state == NEWLINE_TAB_DIR) {
                        nextState = NEWLINE_TAB_DIR;
                    } else if(state == NEWLINE_TAB_POINT || state == NEWLINE_TAB_FILE) {
                        nextState = NEWLINE_TAB_FILE;
                    } else if (state == NEWLINE){
                        nextState = NONE;
                    }
                }
                break;
        }
        return nextState;
    }
    
    int lengthLongestPath(string input) {
        int state = NONE;
        int nextState;
        int innerLength = 0;
        int depth = 0;
        int maxPathSize = 0;
        int currentPathSize;
        vector<int> depthByLength;
        for(int i = 0; i < input.size() && state != ERROR; i++) {
            nextState = getNextInnerState(state, input[i]);
            
            if(nextState == NONE || nextState == NEWLINE_TAB_DIR || nextState == NEWLINE_TAB_FILE || nextState == NEWLINE_TAB_POINT) {
                innerLength++;
            } else if (nextState == NEWLINE_TAB) {
                depth++;
            }
            
            if((nextState == NEWLINE && state != NEWLINE) || i == input.size() - 1) {
                if(depth == 0) {
                    currentPathSize = innerLength;
                } else {
                    currentPathSize = depthByLength[depth - 1] + innerLength + 1;
                }
                if((state == NEWLINE_TAB_FILE || state == NEWLINE_TAB_POINT) && currentPathSize > maxPathSize) {
                    maxPathSize = currentPathSize;
                } else {
                    if(depth == depthByLength.size()){
                        depthByLength.push_back(currentPathSize);
                    } else {
                        depthByLength[depth] = currentPathSize;
                    }
                }
                innerLength = 0;
                depth = 0;
            }
            state = nextState;
        }
        return maxPathSize;
    }
    

    };


Log in to reply
 

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