SimplifyPath [source code]

public class SimplifyPath {
static
/******************************************************************************/
class Solution {
    public String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<> ();
        char[] chp = path.toCharArray ();
        if (chp.length <= 1)
            return path;
        for (int i = 0; i < chp.length; i++) {
            if (chp[i] != '/') {
                int poke = i;
                while (poke < chp.length && chp[poke] != '/')
                    poke++;
                String token = new String (chp, i, poke - i);
                i = poke;
                if (token.equals (".")) {
                    continue;
                } else if (token.equals ("..")) {
                    if (!stack.isEmpty ())
                        stack.pop ();
                } else {
                    stack.push (token);
                }
            }
        }
        if (stack.isEmpty ())
            return chp[0] == '/' ? "/" : "";
        StringBuilder sb = new StringBuilder ();
        while (!stack.isEmpty ()) {
            if (sb.length () > 0 || chp[0] == '/')
                sb.append ("/");
            sb.append (stack.pollLast ());
        }
        return sb.toString ();
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SimplifyPath.Solution tester = new SimplifyPath.Solution();
        String[] inputs = {
            "/home/", "/home",
            "/a/./b/../../c/", "/c",
            "/../", "/",
            "/home//foo/", "/home/foo",
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            String path = inputs[2 * i], ans = inputs[2 * i + 1];
            System.out.println (Printer.separator ());
            String output = tester.simplifyPath (path);
            System.out.printf ("%s -> %s, expected: %s\n", 
                path, Printer.wrap (output, output.equals (ans) ? 92 : 91), ans
            );
        }
    }
}

downvote很多的一个题目, 准备好被虐了;

给的两个Corner Case的第一个好像还是有点印象的, OS的时候学过的, 知识点就是root的.和..都是root(/)自己;

感觉这个题最后难度估计就是各种case的break了, 算法本身并不复杂;

自己写的时候很想用split来直接写, 不过想想真正面试的时候碰到这题很可能会让你自己手动扫描, 还是练一练算了;

另外, Stack算法, 在pop之前先判断peek, 这个也是见过的小技巧了, 其实也可以理解为一个pre leaf的判断;

另外提醒一点, 这题是一个让你simplify的过程, 不是让你跟Pintos上面那样, 去parse; Pintos当时还要先判断一下起点在哪里; 这里其实也有一个稍微类似的相应的处理: 并不是所有的/都是可以直接跳过的;

仔细考虑了之后, 写了上面的算法, 就把题目给的四个test给调出来之后, 一次就AC了, 勉强没有超时; 速度是5ms (98%), 很意外的快;

另外, 看上面用的这个String​(char[] value, int offset, int count)函数; 这个函数对于我这种喜欢用char array的选手来说, 还是要熟悉的, 经常需要用到; 注意arg2是count, 而不是end_index;

另外, String​Builder没有isEmpty ()和size (). 这个以前还真的没有注意过;

试了一下, 才发现这个题目是不handle relative path的; 反正我的算法是可以handle的; 不过既然题目要求简化了, 按理说应该说清楚的; 哦, 人家有说是absolute path, 我自己没看清; 算了, 多写点也不是过错;

在后面调的玩的时候, 发现这题居然还有"/..." -> "/..."这样的test; 这个就很无语了; 不过这个其实没有毛病, 本身文件名是允许包含.的, 比如extension;

没有editorial;

@monaziyi said in C++ 10-lines solution:

C++ also have getline which acts like Java's split. I guess the code can comment itself.

string simplifyPath(string path) {  
    string res, tmp;  
    vector<string> stk;  
    stringstream ss(path);  
    while(getline(ss,tmp,'/')) {  
        if (tmp == "" or tmp == ".") continue;  
        if (tmp == ".." and !stk.empty()) stk.pop_back();  
        else if (tmp != "..") stk.push_back(tmp);  
    }  
    for(auto str : stk) res += "/"+str;  
    return res.empty() ? "/" : res;  
}

其实还是很好理解的, 这个getline好像就跟c的strtok_r还是什么的; 因为人家题目读的仔细, 没有考虑relative path的问题, 所以最后实际上的算法本身还是很简单的;

另外, 他这个代码因为不当的使用了&& in header, 导致代码有一个地方比较蠢, 这个我自己是总结过的:

@rabeeh said in C++ 10-lines solution:

you do not need to check for .. two times, you need to put checking for empty inside the if

class Solution {  
public:  
    string simplifyPath(string path) {  
        string result="", token;  
        stringstream ss(path);  
        vector<string> tokens;  
        while(getline(ss, token, '/')){  
            if(token=="." || token=="") continue;  
            else if(token==".."){  
                if(tokens.size()!=0)  tokens.pop_back();  
            }  
            else tokens.push_back(token);  
        }  
        if(tokens.size()==0) return "/";  
        for(int i=0; i<tokens.size(); ++i)  
            result=result+'/'+tokens[i];  
        return result;  
    }  
};

所以我再次重申, 在header里面的条件并列with && or ||

• 要么是你确定是一个明显的and或者or的关系;
• 要么是你故意用short circuit来保护后面的condition;

感觉这个总结还是不够完整; 重要的其实还是有一个logic tree的概念: !stk.empty()这个本身就不跟tmp == ".."是一个level, 所以不要放到一个header里面;

@shpolsky said in Java 10-lines solution with stack:

Hi guys!

The main idea is to push to the stack every valid file name (not in {"",".",".."}), popping only if there's smth to pop and we met "..". I don't feel like the code below needs any additional comments.

public String simplifyPath(String path) {  
    Deque<String> stack = new LinkedList<>();  
    Set<String> skip = new HashSet<>(Arrays.asList("..",".",""));  
    for (String dir : path.split("/")) {  
        if (dir.equals("..") && !stack.isEmpty()) stack.pop();  
        else if (!skip.contains(dir)) stack.push(dir);  
    }  
    String res = "";  
    for (String dir : stack) res = "/" + dir + res;  
    return res.isEmpty() ? "/" : res;  
}

Hope it helps!

原来LinkedList也有Deque的接口;

@lym5523 said in Java 10-lines solution with stack:

I guess the reason is that stack iterator will not iterate in order as you expected. See this: http://stackoverflow.com/questions/16992758/is-there-a-bug-in-java-util-stacks-iterator

我也被坑过;

submission最优解: 3(99):

class Solution {  
    public String simplifyPath(String path) {  
        char[] res = new char[path.length() + 1];  

        char[] input = path.toCharArray();  
        int slow = 0;  
        int fast = 0;  
        if (input[0] != '/') {  
            res[0] = '/';  
            slow = 1;  
        }  
        while (fast < path.length()) {  
            if (input[fast] == '/') {  
                res[slow++] = input[fast++];  
                while (fast < input.length && input[fast] == '/') {  
                    fast++;  
                }  
            } else if (input[fast] != '.' && input[fast] != '/') {  
                while (fast < input.length && input[fast] != '/') {  
                    res[slow++] = input[fast++];  
                }  
            } else if (input[fast] == '.') {  
                if (fast + 1 == path.length()) {  
                    break;  
                }  
                if (input[fast + 1] == '/') {  
                    fast += 1;  
                    while (fast < input.length && input[fast] == '/') {  
                        fast++;  
                    }  

                } else if (input[fast + 1] != '.' && input[fast + 1] != '/') {  

                    while (fast < input.length && input[fast] != '/') {  
                        res[slow++] = input[fast++];  
                    }  
                } else if (input[fast + 1] == '.') {  
                    if (fast + 2 == path.length()) {  
                        if (slow >= 2) {  
                            slow -= 2;  
                        }  
                        while (slow > 0 && res[slow] != '/') {  
                            slow--;  
                        }  
                        break;  
                    }  
                    if (input[fast + 2] == '/') {  
                        if (slow >= 2) {  
                            slow -= 2;  
                        }  
                        while (slow > 0 && res[slow] != '/') {  
                            slow--;  
                        }  
                        fast += 2;  
                    } else {  
                        while (fast < input.length && input[fast] != '/') {  
                            res[slow++] = input[fast++];  
                        }  
                    }  
                }  
            }  
        }  
        if (slow > 1 && res[slow - 1] == '/') {  
            slow -= 1;  
        }  
        return slow == 0 ? "/" : new String(res, 0, slow);  
    }  
}

又臭又长, 不看了, 大概意思就是直接一边parse一边往result里面丢; 不知道他是怎么处理/a/b/c/../../..这种的, 怎么往回undo呢? 试了一下, 他的这个代码是能搞定的;

哦, 看了一下知道了, 他直接往里面丢的时候, 是同时把/也丢进去的, 所以最后需要倒退的时候, 直接扫到/的位置就行了;

这种算法看看就行了; 可读性太差了;

Problem Description

Given an absolute path for a file (Unix-style), simplify it.

For example,

path = "/home/", => "/home"

path = "/a/./b/../../c/", => "/c"

click to show corner cases.

Corner Cases:

1. Did you consider the case where path = "/../"?
   In this case, you should return "/".
2. Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
   In this case, you should ignore redundant slashes and return "/home/foo".

Difficulty:Medium
Total Accepted:107.1K
Total Submissions:409.6K
Contributor:LeetCode
Companies
facebookmicrosoft
Related Topics
stringstack