Luna Tech

Tutorials For Dummies.

整理字符串(Leetcode)

2020-12-30


1. 题目

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

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

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


2. 思路

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


结语

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