This is the 30th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Recommended reading

  • CSDN home page
  • GitHub open source address
  • Unity3D plugin sharing
  • Jane’s address book
  • My personal blog
  • QQ group: 1040082875

Hello, everyone, I am a little Magic dragon, Unity3D software engineer, VR, AR, virtual simulation direction, update software development skills from time to time, life perception, remember to use one button three links.

A, the title

1. Algorithm topic

“Given an absolute path string for a file or directory in a carton, return a more concise canonical path.”

Title link:

Source: LeetCode

Link: 71. Simplified Paths – LeetCode (leetcode-cn.com)

2

Given a string path representing a Unix-style absolute path (beginning with a ‘/’) to a file or directory, convert it to a more concise canonical path.

In Unix-style file systems, a dot (.) Represents the current directory itself; In addition, two points (..) Indicates that the directory is switched to a higher level (pointing to the parent directory). Both can be part of a complex relative path. Any number of consecutive slashes (that is, ‘//’) are treated as a single slash ‘/’. For this problem, any other format of the point (for example, ‘… ‘) are treated as file/directory names.

Note that the returned canonical path must follow the following format:

  • Always start with a slash ‘/’.
  • Two directory names must be separated by a single slash ‘/’.
  • The last directory name (if present) cannot end in a ‘/’.
  • In addition, a path contains only directories on the path from the root directory to the destination file or directory (that is, no ‘.’ or ‘.. ‘).

Returns the simplified canonical path.

Example 1: Input: path = "/home/" Output: "/home" Description: Note that there is no slash after the last directory name.Copy the code
Example 2: Enter: path = "/.. /" Output: "/" Explanation: Going one step up from the root directory is not feasible because the root directory is the highest level you can reach.Copy the code

Second, the problem solving

1. Analysis of ideas

This problem, first analysis of the meaning, given a path, simplify, there are several cases:

  • Multiple consecutive/are reduced to one /
  • One dot. Indicates the current directory
  • Two points.. Indicates the directory on the computer. You need to return to the previous level

When two points are encountered, you need to go back to the parent directory, similar to popping the top of the stack.

Traverses the path string, if it encounters /, it skips, if it encounters non-slashes, it counts those between the two slashes. Points, a dot represents the peer directory, skipped;

Two dots identify the parent directory and pop the top element of the stack.

If the file name is a string of other characters, it is directly pushed.

2. Code implementation

Code reference:

public class Solution {
    public string SimplifyPath(string path) {
            Stack<string> s = new Stack<string> ();string[] spiltArr = path.Split('/');
            for (int i = 0; i < spiltArr.Length; i++)
            {
                if (spiltArr[i] == "")
                {
                    continue;
                }

                if (spiltArr[i] == "..")
                {
                    if (s.Count > 0) { s.Pop(); }}else if(spiltArr[i] ! =".") { s.Push(spiltArr[i]); }}if(s.Count ! =0)
            {
                StringBuilder sb = new StringBuilder();
                while(s.Count ! =0)
                {
                    sb.Insert(0, s.Pop());
                    sb.Insert(0."/");
                }
                return sb.ToString();
            }
            else
            {
                return "/"; }}}Copy the code

3. Time complexity

Time complexity: O(n)

Each character in a string is traversed at most once.

Space complexity: O(n)

Where n stands for the length of the string.

Third, summary

The Linux directory level is implemented using stacks, and for simplicity, strings are used directly to simulate stack operations.