首页 > 其他 > 详细

Simplify Path

时间:2014-04-11 10:29:42      阅读:341      评论:0      收藏:0      [点我收藏+]

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.


直接在path上进行操作,避免额外空间。 
1. 用cwpos代表当前已经写入的index,每当有新的字符需要加入的时候就先递增cwpos,然后写入 (path[++cwpos= X);
2. 用一对偏移表示当前找到的一个介于两个‘/‘之间的串,cstart和cend(cend也可能是末尾标识‘\0‘)
3. 这样一来clen = cend - cstart就是当前需要附加到返回结果的串(记为s)。 这时分别考虑s为空,s== ‘.‘ , s==‘..‘ 以及其他一共四种情况,前两种情况都直接忽略,直接更新cstart = cend进入下次循环; 如果是“..”, 从当前cwpos开始向前找前一个‘/’,并更新cwpos, 如果是其他则写入‘/‘和s,同时更新cwpos。



class Solution {
public:
    string simplifyPath(string path) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        int len = path.length();
        int cwpos = -1, cstart = 0, cend = 0;
        while (true) {
            while (cstart < len && path[cstart] == ‘/‘) ++cstart;
            if (cstart >= len) break;
            cend = cstart + 1;
            while (cend < len && path[cend] != ‘/‘) ++cend;
            int clen = cend - cstart;
            if (clen > 0 && (clen != 1 || path[cstart] != ‘.‘)) {
                if (clen == 2 && path[cstart] == ‘.‘ && path[cstart + 1] == ‘.‘) {
                    while (cwpos >= 0 && path[cwpos] != ‘/‘) --cwpos;
                    if (cwpos >= 0)
                        --cwpos;
                } else {
                    path[++cwpos] = ‘/‘;
                    while (cstart < cend) {
                        path[++cwpos] = path[cstart++];
                    }
                }
            }
            
            cstart = cend;
        }
        
        if (cwpos < 0) return "/";
        path.resize(cwpos + 1);
        return path;
    }
};


Simplify Path,布布扣,bubuko.com

Simplify Path

原文:http://blog.csdn.net/icomputational/article/details/23390003

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!