Luna Tech | 整理字符串（Leetcode）

December 30, 2020 字数 392 1 min

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；

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


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。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25



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();
	}
}