Leetcode: Simplify Path

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:

• Did you consider the case where path = "/../"?
  In this case, you should return "/".
• 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".

Understand the problem:
The problem requires some background of the UNIX command. The string is partitioned by  / .... /. So the basic idea is to check the substring between two / /. 
If the substring equals to '.', simply bypass it because it means the under the current path
If the substring equals to '..', pop the stack
If the substring equals to 'abc', push it into the stack. 

So as analyzed above, the basic idea is to use a stack and maintain the stack elements. 

Solution:

public class Solution {
    public String simplifyPath(String path) {
        if (path == null || path.length() == 0) {
            return "";
        }
        
        Stack<String> stack = new Stack<String>();
        
        int i = 0;
        while (i < path.length()) {
            // bypass the first /
            while (i < path.length() && path.charAt(i) == '/') {
                i++;
            }
            
            int start = i;
            
            if (i == path.length()) {
                break;
            }
            
            // reach the end /
            while(i < path.length() && path.charAt(i) != '/') {
                i++;
            }
            
            int end = i;
            
            String curr = path.substring(start, end);
            if (curr.equals("..")) {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else if (!curr.equals(".")) {
                stack.push(curr);
            }
        }
        
        if (stack.isEmpty()) {
            return "/";
        }
        
        StringBuilder sb = new StringBuilder();
        
        String[] arr = stack.toArray(new String[stack.size()]);
        for (int j = 0; j < arr.length; j++) {
            sb.append('/');
            sb.append(arr[j]);
        }
        
        return sb.toString();
    }
}

Discussion:
There are several very important take away messages for this question. 

• For the line 30 and 34, we used equals() method instead of ==. What is the difference between the two at Java? Basically, == checks for two objects point to the same reference, i.e, memory location. So 

Example 1:

String str1 = "abc";
String str2 = "abc";
if (str1 == str2), it may returns thef false. (NOTE that it could return the true because Java use string poll to implement the string. So the two strings might point to the same memory location).

Example2:
String str1 = "abc";
String str2 = "abcdef";
String str3 = substring(0, 3);
if (str1 == str2) will definitely return false, since they don't point to the same location.

Example3:
String str1 = "abc";
String str2 = str1;
if (str1 == str2), it will definitely return the true, since str2 points to the same memory address of the str1.

• The Object1.equals(Ojbect2) will check the contents of the two objects. So the first example shown above will definitely return the true. As a result, if we wanna compare the contents of the two objects, use equals instead of ==. If we wanna check if two objects points to the same memory address, use ==. 
• That rule applies only Java reference type. For primitive data types like char, use == only will check the contents for two characters. Note that primitive data types do not have the equals method. 

The second take array message is the iterator of the stack. 

import java.util.*;

public class Test {
  public static void main(String[] args) {
    Stack<String> stack = new Stack<String>();

    stack.push("a");
    stack.push("b");
    stack.push("c");
    
    for (String s : stack) {
      System.out.println(s);
    }
  }
}

The output will be "a" "b" "c" instead of b, c, a. Be careful of that "bugs" in Java design. Basically, it iterates the order where you push into the stack. 

A neat code:
For that problem, we can write a neater code as below. The point is to use split() method to remove the '/' characters. 

public class Solution {
    public String simplifyPath(String path) {
        if (path == null || path.length() == 0) {
            return "";
        }
        
        String delim = "[/]+";
        String[] arr = path.split(delim);
        
        Stack<String> stack = new Stack<String>();
        
        for (String str : arr) {
            if(str.equals("/")){
                continue;
            }
            if (str.equals("..")) {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else if (!str.equals(".") && !str.isEmpty()) {
                stack.push(str);
            }
        }
        
        StringBuilder sb = new StringBuilder();
        if (stack.isEmpty()) {
            return "/";
        }
        
        for (String str : stack) {
            sb.append("/" + str);
        }
        
        return sb.toString();
    }
}

Summary:
The crux of the problem is to extract what you should address from the problem. If you can understand the key to the problem is to check substrings between two slashes, you've got the half done.