
问题
给定 S 和 T 两个字符串,当它们分别被输入到空白的文本编辑器后,判断二者是否相等,并返回结果。 # 代表退格字符。
输入:S = “ab#c”, T = “ad#c”
输出:true
解释:S 和 T 都会变成 “ac”。
输入:S = “ab##”, T = “c#d#”
输出:true
解释:S 和 T 都会变成 “”。
输入:S = “a##c”, T = “#a#c”
输出:true
解释:S 和 T 都会变成 “c”。
输入:S = “a#c”, T = “b”
输出:false
解释:S 会变成 “c”,但 T 仍然是 “b”。
提示:
- 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.
Input: S = “ab#c”, T = “ad#c”
Output: true
Explanation: Both S and T become “ac”.
Input: S = “ab##”, T = “c#d#”
Output: true
Explanation: Both S and T become “”.
Input: S = “a##c”, T = “#a#c”
Output: true
Explanation: Both S and T become “c”.
Input: S = “a#c”, T = “b”
Output: false
Explanation: S becomes “c” while T becomes “b”.
Note:
- 1 <= S.length <= 200
- 1 <= T.length <= 200
- S and T only contain lowercase letters and ‘#’ characters.
示例
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种算法实现,以下是这个案例的输出结果:
True False
分析:
设 S 和 T 两个单词中最长的单词的字符数为 n,那么显而易见,以上2种算法的时间复杂度均为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4030。