Thinking process

• I need to parse the input
• what's the pattern you found of the input?
• Do I need to do the parsing first? Or I can use it at the same time w/o using extra space?
• Since I need to remember the levels before, what data structure I can apply here? ArrayList vs Stack?

Mistakes I made

• consistency

  • totalCount added 1 then when level is removed, an extra one should removed as well

• 先实现功能 不要为了不必要的耍酷 导致错误

  • if 和 while 那里

• Why using Stack?

  • the pattern of input is LIFO

Terminology

• "\n" is backslash n

https://www.owasp.org/index.php/Password_special_characters

API Methods

String

• lastIndexOf("\t")
• split("\n")
• contains(".")

https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#contains(java.lang.CharSequence))

>>>>>good version >>> Using Stack

public class Solution {
    public int lengthLongestPath(String input) {
        Stack<Integer> stack = new Stack<>();
        stack.add(0);
        int max = 0;

        for (String str : input.split("\n")) {
            int level = str.lastIndexOf("\t") + 1;
            int len = str.length() - level;
            while (stack.size() > level + 1) {
                stack.pop();
            }

            if (str.contains(".")) {
                max = Math.max(max, stack.peek() + len);
            } else {
                stack.push(stack.peek() + len + 1);
            }
        }

        return max;
    }
}

>>>>>bad version >>> Using ArrayList

• use more space than stack

public class Solution {
    public int lengthLongestPath(String input) {
        int totalCount = 0;
        int max = 0;
        int prevLevel = -1;
        ArrayList<Integer> levels = new ArrayList<>();//number of characters in each level so far
        levels.add(0);

        String[] strs = input.split("\n");

        for (String str : strs) {
            int level = str.lastIndexOf('\t') + 1;
            int len = str.length() - level;


            if (prevLevel >= level) {
                while (prevLevel > level) {
                    totalCount = totalCount - levels.get(prevLevel) - 1;
                    prevLevel--;
                }
                totalCount = totalCount - levels.get(prevLevel) - 1;
            }

            prevLevel = level;
            levels.add(level, len);
            totalCount = totalCount + len + 1;

            if (str.contains(".")) {
                max = Math.max(max, totalCount - 1);
            }

        }

        return max;
    }
}