题解 | 路径打印

法一

先对字符串排序，相同前缀的路径下标是连续的

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 15;
string s[N];

// "a\b\c"  -->  ["a", "b", "c"]
vector<string> split(string &s) {
	vector<string> res;
	
	string temp = "";
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '\\') {
			if (temp.size()) {
				res.push_back(temp);   // 遇到 '\' 当前目录加入数组
				temp = "";
			}
		}
		else {
			temp += s[i];              // 没遇到 '\' 记录当前目录名称
		}
	}

	if (temp.size())
		res.push_back(temp);           // 最后一个目录要加入数组

	return res;
}


int main() {
	int n;

	vector<string> cur, pre;

	while (cin >> n, n != 0) {
		pre.clear();

		for (int i = 0; i < n; i++) cin >> s[i];

		// 排序后，相同前缀的目录串下标一定连续
		sort(s, s + n);

		for (int i = 0; i < n; i++) {
			cur = split(s[i]);

			// 相同的前缀不输出
			int st = 0;
			while (st < pre.size() && st < cur.size() && pre[st] == cur[st]) 
				st++;

			while (st < cur.size()) {
				cout << string(st * 2, ' ');    // 输出多个空格
				cout << cur[st] << endl;
				st++;
			}
			pre = cur;
		}
		cout << endl;
	}
}

法二

用数组形式的 trie树 保存 & 遍历

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

const int N = 15, M = N * 50;
string s[N];

int idx;
map<string, int> son[M];   // trie树，且每个结点的分支为字典序

// trie 树插入结点
void insert(vector<string> paths) {
	int p = 0;

	for (auto& path : paths) {
		if (!son[p].count(path))
			son[p][path] = ++idx;
		p = son[p][path];
	}
}


// 先序遍历trie树并打印
void dfs(int u, int depth) {
	for (auto &p : son[u]) {
		// 输出          空格         +     目录  +   换行
		cout << string(depth * 2, ' ') << p.first << endl;  // 先访问根
		dfs(p.second, depth + 1);                           // 再访问其余分支
	}
}


// "a\b\c"  -->  ["a", "b", "c"]
vector<string> split(string& s) {
	vector<string> res;

	string temp = "";
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '\\') {
			if (temp.size()) {
				res.push_back(temp);   // 遇到 '\' 当前目录加入数组
				temp = "";
			}
		}
		else {
			temp += s[i];              // 没遇到 '\' 记录当前目录名称
		}
	}

	if (temp.size())
		res.push_back(temp);           // 最后一个目录要加入数组

	return res;
}



int main() {
	int n;
	while (cin >> n, n != 0) {

		idx = 0;
		for (int i = 0; i < M; i++)
			son[i].clear();            // 清理trie树

		while (n--) {
			string s;
			cin >> s;

			auto path = split(s);      // 拆成目录数组
			insert(path);              // 插入trie树
		}

		dfs(0, 0);                     // 遍历trie树并输出
		cout << endl;
	}
}