整理字符串（Leetcode）

2020-12-30

1. 题目

https://leetcode-cn.com/problems/make-the-string-great/

https://leetcode.com/problems/make-the-string-great/

去掉字符串里面大小写不同的同一个字母。

Aa => 空字符串
AA => AA
aABbc => c

2. 思路

用 stack 来存 character，每个 character 和 stack 的第一个 char 作比较，假如是大小写不同的同一个字母，pop 这个 char；
最后返回 stack 里面剩余的字母组成的 string；

public class Solution
{
	public string MakeGood(string s)
	{
		if (s.Length < 2)
			return s;
		Stack<char> stack = new Stack<char>();
		char[] arr = s.ToCharArray();
		foreach(char c in arr){
			if (stack.Count() == 0)
				stack.Push(c);
			else {
				if (stack.Peek() != c && stack.Peek().ToString().ToLower() == c.ToString().ToLower())
					stack.Pop();
				else
					stack.Push(c);
			}
		}
		StringBuilder sb = new StringBuilder();
		sb.Append(stack.Reverse().ToArray());
		return sb.ToString();
	}
}

3. 优化

参考了别人的解题思路之后，发现判断两个 char 是否为大小写不同的同一个字母可以用一种更简单的方法： Math.Abs(c1-c2) == 32

这个方法用到了字母的编码，每个字母有一个对应的数字，大小写相减正好是 32。


public class Solution
{
	public string MakeGood(string s)
	{
		if (s.Length < 2)
			return s;
		Stack<char> stack = new Stack<char>();
		char[] arr = s.ToCharArray();
		foreach(char c in arr){
			if (stack.Count() == 0)
				stack.Push(c);
			else {
				// a better way of checking same character with different case
				if (stack.Peek() != c && Math.Abs(stack.Peek()-c) == 32)
					stack.Pop();
				else
					stack.Push(c);
			}
		}
		StringBuilder sb = new StringBuilder();
		sb.Append(stack.Reverse().ToArray());
		return sb.ToString();
	}
}

结语

欢迎大家分享更好的解法~