问题
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/4030 访问。
给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
提示：
- 1 <= S.length <= 200
- 1 <= T.length <= 200
- S 和 T 只含有小写字母以及字符 '#'。
Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.
Note:
- 1 <= S.length <= 200
- 1 <= T.length <= 200
- S and T only contain lowercase letters and '#' characters.
示例
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/4030 访问。
public class Program {
public static void Main(string[] args) {
var S = "ab#c";
var T = "ad#c";
var res = BackspaceCompare(S, T);
Console.WriteLine(res);
S = "a#c";
T = "b#cd";
res = BackspaceCompare2(S, T);
Console.WriteLine(res);
Console.ReadKey();
}
private static bool BackspaceCompare(string S, string T) {
var stackS = GetStack(S);
var stackT = GetStack(T);
if(stackS.Count != stackT.Count) return false;
for(var i = 0; i < stackS.Count; i++) {
if(stackS.ElementAt(i) != stackT.ElementAt(i))
return false;
}
return true;
}
private static Stack<char> GetStack(string S) {
var stack = new Stack<char>();
foreach(var c in S) {
if(c == '#') {
if(stack.Count != 0) stack.Pop();
} else {
stack.Push(c);
}
}
return stack;
}
private static bool BackspaceCompare2(string S, string T) {
var sb1 = GetStringBuilder(S);
var sb2 = GetStringBuilder(T);
return sb1.ToString() == sb2.ToString();
}
private static StringBuilder GetStringBuilder(string S) {
var sb = new StringBuilder();
for(var i = 0; i < S.Length; ++i) {
if(S[i] == '#') {
if(sb.Length > 0) sb.Remove(sb.Length - 1, 1);
} else sb.Append(S[i]);
}
return sb;
}
}以上给出2种算法实现，以下是这个案例的输出结果：
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/4030 访问。
True
False分析：
设 S 和 T 两个单词中最长的单词的字符数为 n，那么显而易见，以上2种算法的时间复杂度均为： 。