[leetcode #71] Simplify Path

Problem

Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period '.' refers to the current directory, a double period '..' refers to the directory up a level, and any multiple consecutive slashes (i.e. '//') are treated as a single slash '/'. For this problem, any other format of periods such as '...' are treated as file/directory names.

The canonical path should have the following format:

・ The path starts with a single slash '/'.
・ Any two directories are separated by a single slash '/'.
・ The path does not end with a trailing '/'.
・ The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period '.' or double period '..')

Return the simplified canonical path.

Example 1:

Input: path = "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.

Example 2:

Input: path = "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.

Example 3:

Input: path = "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.

Constraints:

・ 1 <= path.length <= 3000
・ path consists of English letters, digits, period '.', slash '/' or '_'.
・ path is a valid absolute Unix path.

Idea

주어진 절대 경로를 canonical path로 간단히 만들라는 문제다. input으로 주어지는 값은 유효한 경로이므로 해당 부분에 대해서는 확인할 필요는 없다.

String과 관련된 함수를 사용하면 쉽게 풀 수 있다. 우선 directory의 기준점이 되는 '/'를 기준으로 substring으로 나누고 해당 문자열을 list에 넣는다.

만약 ".."가 나왔을 경우 list의 가장 마지막 directory를 제거한다. substring이 "."거나 빈 문자열일 때 ("//"인 경우)를 제외하면 directory를 list에 넣는다.

마지막 "/"가 등장한 후에도 path가 남아있을 수 있으므로 위에서 substring을 처리한 방법으로 마지막 directory를 처리한다.

list에 남아있는 건 canonical path에 들어갈 directory이므로 해당 directory 사이에 "/"를 넣으면서 경로를 완성한 후 리턴한다.

Solution

class Solution {
    public String simplifyPath(String path) {
        List<String> list = new LinkedList<>();
        int firstIndex = 1;
        int secondIndex = 1;

        while (true) {
            secondIndex = path.indexOf('/', firstIndex);
            if (secondIndex < 0) {
                break;    
            }

            String dict = path.substring(firstIndex, secondIndex);
            firstIndex = secondIndex+1;

            if ("..".equals(dict)) {
                if (!list.isEmpty()) {
                    list.remove(list.size()-1);
                }
            } else if (!".".equals(dict) && !"".equals(dict)) {
                list.add(dict);
            } 
        }

        if (firstIndex != path.length()) {
            String dict = path.substring(firstIndex);
            if ("..".equals(dict)) {
                if (!list.isEmpty()) {
                    list.remove(list.size()-1);
                }
            } else if (!".".equals(dict) && !"".equals(dict)) {
                list.add(dict);
            }
        }

        StringBuilder builder = new StringBuilder();

        if (list.isEmpty()) {
            return "/";
        }

        while (!list.isEmpty()) {
            builder.append("/");
            builder.append(list.remove(0));
        }

        return builder.toString();
    }
}

Reference

https://leetcode.com/problems/simplify-path/