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. 思路

  1. 用 stack 来存 character,每个 character 和 stack 的第一个 char 作比较,假如是大小写不同的同一个字母,pop 这个 char;
  2. 最后返回 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();
	}
}

结语

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


Talk to Luna


Support Luna