LeetCode第1047题 – 删除字符串中的所有相邻重复项

85 views

题目

给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。
在 S 上反复执行重复项删除操作,直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

解答

class Solution {
    public String removeDuplicates(String S) {
		if (S.length() == 1) {
			return S;
		}

		LinkedList<String> list = new LinkedList<>();
		list.add(String.valueOf(S.charAt(0)));

		for (int i = 1, length = S.length(); i < length; ++i) {
			char c = S.charAt(i);
			String s = String.valueOf(c);
			if (!list.isEmpty() && list.getFirst().equals(s)) {
				list.pop();
			} else {
				list.addFirst(s);
			}
		}

		StringBuilder sb = new StringBuilder();
		while (!list.isEmpty()) {
			sb.insert(0, list.removeFirst());
		}

		return sb.toString();
    }
}

要点

当前的解法,效率上似乎存在问题,后续要考虑更加高效的方案。



若非注明,均为原创,欢迎转载,转载请注明来源:LeetCode第1047题 – 删除字符串中的所有相邻重复项

关于 JackieAtHome

基层程序员,八年之后重新启航

此条目发表在 Java, LeetCode 分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Protected with IP Blacklist CloudIP Blacklist Cloud