LeetCode - Medium - 71. Simplify Path

ゞ浴缸里的玫瑰 2022-11-17 05:27 147阅读 0赞

## Topic ##

*  String
 *  Stack

## Description ##

[https://leetcode.com/problems/simplify-path/][https_leetcode.com_problems_simplify-path]

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.

**Example 4:**

Input: path = "/a/./b/../../c/"
    Output: "/c"

**Constraints:**

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

## Analysis ##

略

## Submission ##

import java.util.LinkedList;
    
    public class SimplifyPath { 
    
    	// 方法一：我写的
    	public String simplifyPath(String path) { 
    		LinkedList<String> dirs = new LinkedList<>();
    		for (int p1 = 0, p2 = 1; p2 <= path.length(); p2++) { 
    
    			if (p2 == path.length() || path.charAt(p2) == '/') { 
    				String dir = path.substring(p1 + 1, p2);
    				p1 = p2;
    
    				if (dir.equals("") || dir.equals("."))
    					continue;
    
    				if (dir.equals("..")) { 
    					if (!dirs.isEmpty())
    						dirs.removeLast();
    				} else { 
    					dirs.add(dir);
    				}
    			}
    		}
    
    		StringBuilder sb = new StringBuilder();
    		dirs.stream().forEach(dir -> sb.append("/").append(dir));
    		return sb.length() == 0 ? "/" : sb.toString();
    	}
    
    	// 方法二：别人写的，写得更简洁
    	public String simplifyPath2(String path) { 
    		LinkedList<String> list = new LinkedList<>();
    		for (String cur : path.split("/")) { 
    			if (cur.equals("..")) { 
    				if (!list.isEmpty())
    					list.removeLast();
    			} else if (cur.length() > 0 && !cur.equals("."))
    				list.add(cur);
    		}
    		return "/" + String.join("/", list);
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    public class SimplifyPathTest { 
    
    	@Test
    	public void test() { 
    		SimplifyPath obj = new SimplifyPath();
    
    		assertEquals("/home", obj.simplifyPath("/home/"));
    		assertEquals("/", obj.simplifyPath("/../"));
    		assertEquals("/home/foo", obj.simplifyPath("/home//foo/"));
    		assertEquals("/c", obj.simplifyPath("/a/./b/../../c/"));
    
    		assertEquals("/home", obj.simplifyPath2("/home/"));
    		assertEquals("/", obj.simplifyPath2("/../"));
    		assertEquals("/home/foo", obj.simplifyPath2("/home//foo/"));
    		assertEquals("/c", obj.simplifyPath2("/a/./b/../../c/"));
    
    	}
    }

[https_leetcode.com_problems_simplify-path]: https://leetcode.com/problems/simplify-path/