[解题思路] 利用栈的特性,如果substring element 1. 等于“/”,跳过,直接开始寻找下一个element 2. 等于“.”,什么都不需要干,直接开始寻找下一个element 3. 等于“..”,弹出栈顶元素,寻找下一个element 4. 等于其他,插入当前elemnt为新的栈顶,寻找下一个element 最后,再根据栈的内容,重新拼path。这样可以避免处理连续多个“/”的问题。 1: string simplifyPath(string path) { 2: // Start typing your C/C++ solution below 3: // DO NOT write int main() function 4: vector<string> stack; 5: assert(path[0]=='/'); 6: int i=0; 7: while(i< path.size()) 8: { 9: while(path[i] =='/' && i< path.size()) i++; //skip the begining '////' 10: if(i == path.size()) 11: break; 12: int start = i; 13: while(path[i]!='/' && i< path.size()) i++; //decide the end boundary 14: int end = i-1; 15: string element = path.substr(start, end-start+1); 16: if(element == "..") 17: { 18: if(stack.size() >0) 19: stack.pop_back(); 20: } 21: else if(element!=".") 22: stack.push_back(element); 23: } 24: if(stack.size() ==0) return "/"; 25: string simpPath; 26: for(int i =0; i<stack.size(); i++) 27: simpPath += "/" + stack[i]; 28: return simpPath; 29: }
Thursday, October 23, 2014
Simplify Path
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment