問題

Unixスタイルの絶対パス（'/'で始まる文字列）が与えられた場合、それを簡略化された標準パスに変換してください。

Unixファイルシステムでは、ドット（.）は現在のディレクトリを表し、2つのドット（..）は親ディレクトリ（1レベル上）に移動を表します。これらは両方とも、相対パスの一部として使用できます。複数の連続するスラッシュ（'//'）は、単一のスラッシュ'/'として扱われます。それ以外のドット形式（例：'...'）は、ファイルまたはディレクトリ名として扱われます。

返される標準パスは以下の条件を満たす必要があります：

• 常にスラッシュ'/'で始まる
• 2つのディレクトリ名の間には1つのスラッシュのみ
• 最後のディレクトリ名（存在する場合）は'/'で終わらない
• パスにはルートディレクトリからターゲットファイルまたはディレクトリまでのディレクトリのみが含まれる（'.'や'..'は含まない）

例

例1：
入力：path = "/home/"
出力："/home"
説明：最後のディレクトリ名の後にスラッシュはありません。

例2：
入力：path = "/../"
出力："/"
説明：ルートディレクトリから上に移動することはできません。

例3：
入力：path = "/home//foo/"
出力："/home/foo"
説明：標準パスでは、複数の連続するスラッシュは1つのスラッシュに置き換える必要があります。

例4：
入力：path = "/a/./b/../../c/"
出力："/c"

制約：
1 <= path.length <= 3000
pathは英字、数字、'.'、'/'または'_'で構成されます。
pathは有効なUnixスタイルの絶対パスです。

データ構造：スタック

スタックは、后入れ先出し（LIFO）原則に従う一般的なデータ構造です。スタックには2つの主要な操作があります：プッシュ（push）とポップ（pop）です。プッシュ操作は要素をスタックの上部に追加し、ポップ操作はスタックの上部から要素を取り除いて返します。

以下は、スタックのJava実装例です：

import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.List;

public class Stack<T> {
    private List<T> elements;

    public Stack() {
        elements = new ArrayList<>();
    }

    public void push(T item) {
        elements.add(item);
    }

    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        int topIndex = elements.size() - 1;
        T item = elements.get(topIndex);
        elements.remove(topIndex);
        return item;
    }

    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return elements.get(elements.size() - 1);
    }

    public boolean isEmpty() {
        return elements.isEmpty();
    }

    public int size() {
        return elements.size();
    }
}

この実装では、ArrayListを使用してスタックの要素を保存します。pushメソッドはリストの末尾に要素を追加し、popメソッドはリストの末尾から要素を取り除いて返します。peekメソッドは要素を取り除くことなくスタックの最上位の要素を返します。isEmptyメソッドはスタックが空かどうかをチェックし、sizeメソッドはスタックのサイズを返します。

使用例：

public class Main {
    public static void main(String[] args) {
        Stack<String> pathStack = new Stack<>();
        pathStack.push("home");
        pathStack.push("user");
        pathStack.push("documents");

        System.out.println(pathStack.pop());  // 出力：documents
        System.out.println(pathStack.peek()); // 出力：user
        System.out.println(pathStack.size()); // 出力：2
        System.out.println(pathStack.isEmpty()); // 出力：false
    }
}

解答コード

import java.util.Stack;
import java.util.Arrays;

public class Solution {
    public String simplifyPath(String path) {
        String[] parts = path.split("/");
        Stack<String> directoryStack = new Stack<>();

        for (String part : parts) {
            if (part.equals("..")) {
                if (!directoryStack.isEmpty()) {
                    directoryStack.pop();
                }
            } else if (!part.equals(".") && !part.isEmpty()) {
                directoryStack.push(part);
            }
        }

        if (directoryStack.isEmpty()) {
            return "/";
        }

        StringBuilder result = new StringBuilder();
        for (String dir : directoryStack) {
            result.append("/").append(dir);
        }

        return result.toString();
    }
}

解法説明

このJavaコードは、ファイルパスを簡略化する機能を実現しています。例えば、"/a/b/c/../../x/"のような入力が与えられた場合、"/x"に変換します。

主な考え方は、スタックを使用してディレクトリの移動をシミュレートすることです。まず、パス文字列を"/"で分割して文字列配列を取得します。次に、配列内の各要素を順序通りに処理します。

現在の要素が".."の場合、親ディレクトリに戻る必要があることを意味するため、スタックから要素をポップします。現在の要素が"."でも空文字列でもない場合、有効なディレクトリ名としてスタックにプッシュします。

配列の処理完了後、スタックに要素が残っている場合、それが最終的なパスを表します。スタックが空の場合は、ルートディレクトリ"/"を返します。最後に、スタック内の要素を"/"で連結して、簡略化されたパスを構築します。

このアルゴリズムの時間計算量はO(n)であり、nはパス文字列の長さです。空間計算量はO(n)で、スタックに 저장されるディレクトリ名を 저장するためです。