0242. Valid Anagram

242. Valid Anagram #

题目 #

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:


Input: s = "anagram", t = "nagaram"
Output: true

Example 2:


Input: s = "rat", t = "car"
Output: false

Note:

You may assume the string contains only lowercase alphabets.

Follow up:

What if the inputs contain unicode characters? How would you adapt your solution to such case?

题目大意 #

给出 2 个字符串 s 和 t,如果 t 中的字母在 s 中都存在,输出 true,否则输出 false。

解题思路 #

这道题可以用打表的方式做。先把 s 中的每个字母都存在一个 26 个容量的数组里面,每个下标依次对应 26 个字母。s 中每个字母都对应表中一个字母,每出现一次就加 1。然后再扫字符串 t,每出现一个字母就在表里面减一。如果都出现了,最终表里面的值肯定都是 0 。最终判断表里面的值是否都是 0 即可,有非 0 的数都输出 false 。

代码 #


package leetcode

// 解法一
func isAnagram(s string, t string) bool {
	alphabet := make([]int, 26)
	sBytes := []byte(s)
	tBytes := []byte(t)
	if len(sBytes) != len(tBytes) {
		return false
	}
	for i := 0; i < len(sBytes); i++ {
		alphabet[sBytes[i]-'a']++
	}
	for i := 0; i < len(tBytes); i++ {
		alphabet[tBytes[i]-'a']--
	}
	for i := 0; i < 26; i++ {
		if alphabet[i] != 0 {
			return false
		}
	}
	return true
}

// 解法二
func isAnagram1(s string, t string) bool {
	if s == "" && t == "" {
		return true
	}
	if s == "" || t == "" {
		return false
	}
	sBytes := []byte(s)
	tBytes := []byte(t)
	if len(sBytes) != len(tBytes) {
		return false
	}
	quickSortByte(sBytes, 0, len(sBytes)-1)
	quickSortByte(tBytes, 0, len(tBytes)-1)

	for i := 0; i < len(sBytes); i++ {
		if sBytes[i] != tBytes[i] {
			return false
		}
	}
	return true
}
func partitionByte(a []byte, lo, hi int) int {
	pivot := a[hi]
	i := lo - 1
	for j := lo; j < hi; j++ {
		if a[j] > pivot {
			i++
			a[j], a[i] = a[i], a[j]
		}
	}
	a[i+1], a[hi] = a[hi], a[i+1]
	return i + 1
}
func quickSortByte(a []byte, lo, hi int) {
	if lo >= hi {
		return
	}
	p := partitionByte(a, lo, hi)
	quickSortByte(a, lo, p-1)
	quickSortByte(a, p+1, hi)
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者