KK's blog

LeetCode 438 Find All Anagrams in a String

Posted on 2022-02-15 Edited on 2026-06-04 Disqus:

Given two strings s and p, return an array of all the start indices of p‘s anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = “cbaebabacd”, p = “abc”
Output: [0,6]
Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.

Example 2:

Input: s = “abab”, p = “ab”
Output: [0,1,2]
Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.

Constraints:

`1 <= s.length, p.length <= 3 10⁴*sandp` consist of lowercase English letters.

题目大意：

求字符串s中含p的anagram的所有初始下标

解题思路：

求某子串的频率统计，第一时间想到滑动窗口。此题较特殊，属于固定大小窗口的滑动窗口，因为p的大小是固定的，窗口大小必须和p长度一样。

解题步骤：

此题可以跟LeetCode 438一样，用两个map直接比较，不用unique_count，但时间复杂度变成nm，m为p的长度

注意事项：

Python代码：

def findAnagrams(self, s: str, p: str) -> List[int]:
	char_to_count_p = collections.Counter(p)
	substr_win = collections.defaultdict(int)
	res = []
	for i, char in enumerate(s):
		substr_win[s[i]] += 1
		# window: [i - len(p) + 1, i]
		if i >= len(p):
			substr_win[s[i - len(p)]] -= 1
			if substr_win[s[i - len(p)]] == 0:
				substr_win.pop(s[i - len(p)])
		if substr_win == char_to_count_p:
			res.append(i - len(p) + 1)
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

LeetCode 567 Permutation in String

Posted on 2022-02-15 Edited on 2026-06-03 Disqus:

LeetCode

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1‘s permutations is the substring of s2.

Example 1:

Input: s1 = “ab”, s2 = “eidbaooo”
Output: true
Explanation: s2 contains one permutation of s1 (“ba”).

Example 2:

Input: s1 = “ab”, s2 = “eidboaoo”
Output: false

Constraints:

1 <= s1.length, s2.length <= 10<sup>4</sup> s1 and s2 consist of lowercase English letters.

题目大意：

求字符串s2中是否含s1的anagram

解题思路：

类似于LeetCode 438 Find All Anagrams in a String, 唯一区别是substr_win == char_to_count_p时返回而不是加入到res

解题步骤：

N/A

注意事项：

Python代码：

def checkInclusion(self, s1: str, s2: str) -> bool:
	char_to_count_p = collections.Counter(s1)
	substr_win = collections.defaultdict(int)
	for i, char in enumerate(s2):
		substr_win[s2[i]] += 1
		# window: [i - len(p) + 1, i]
		if i >= len(s1):
			substr_win[s2[i - len(s1)]] -= 1
			if substr_win[s2[i - len(s1)]] == 0:
				substr_win.pop(s2[i - len(s1)])
		if substr_win == char_to_count_p:
			return True
	return False

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

LeetCode 670 Maximum Swap

Posted on 2022-02-15 Edited on 2026-06-03 Disqus:

LeetCode

You are given an integer num. You can swap two digits at most once to get the maximum valued number.

Return the maximum valued number you can get.

Example 1:

Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:

Input: num = 9973
Output: 9973
Explanation: No swap.

Constraints:

* 0 <= num <= 10<sup>8</sup>

题目大意：

给定一个数，最多交换一位，使得这个数尽可能最大

解题思路：

类似于LeetCode 854 K-Similar Strings, 如2736，求2后面最大的数为7，和7交换即为所求。这里有两个问题：

第一位可能已经是最大的数位，这样需要遍历每个数位，找到能交换的数位，若这个位在倒序排序后位置一样，表明此位不能交换。所以排序法的算法复杂度为n平方
若要优化就要采用bucket sort，因为数位是有限的。若后续数位有一个数比自己大，表示可交换。所以只要记录每个数位的位置，贪心法从9(最大)遍历到自己，若该位位置在自己之后，可交换
若不同数位上数值相同，应该记录其最后的位置，因为交换时候将小的尽量往后交换，越好越不重要，如2949, 2和最后的9交换得到最大的数

解题步骤：

N/A

注意事项：

内循环从9遍历到该位数值(不包括)
buckets的key为字符串，注意整数和字符串互换，如buckets[str(j)], int(digits[i])

Python代码：

def maximumSwap(self, num: int) -> int:
	digits, buckets = str(num), collections.defaultdict(int)
	for i, digit in enumerate(digits):
		buckets[digit] = i # use last position for same char
	for i in range(len(digits)):
		for j in range(9, int(digits[i]), -1): # remember to use int(digits[i]) not i
			if buckets[str(j)] > i: # 2736, i = (2), j = (7) # remember to use str j
				return int(digits[:i] + digits[buckets[str(j)]] + digits[i + 1:buckets[str(j)]] + digits[i] + digits[buckets[str(j)] + 1:])
	return num

算法分析：

时间复杂度为O(9n)，空间复杂度O(n)

LeetCode 854 K-Similar Strings

Posted on 2022-02-15 Edited on 2026-06-03 Disqus:

LeetCode

Strings s1 and s2 are k-similar (for some non-negative integer k) if we can swap the positions of two letters in s1 exactly k times so that the resulting string equals s2.

Given two anagrams s1 and s2, return the smallest k for which s1 and s2 are k-similar.

Example 1:

Input: s1 = “ab”, s2 = “ba”
Output: 1

Example 2:

Input: s1 = “abc”, s2 = “bca”
Output: 2

Constraints:

1 <= s1.length <= 20 s2.length == s1.length
s1 and s2 contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}. s2 is an anagram of s1.

题目大意：

两字符，交换两个位置，使得他们相等，求最小交换次数

解题思路：

最值考虑用BFS，难点在于生成neighbor，见注意事项

解题步骤：

N/A

注意事项：

用例子写程序node = abc s2 = cba, 先找到第一个不同位i，然后找下一个不同位j，这个不同位node[j]需要与目标s2[i]相同，贪心法
倒数第二行要break，否则TLE，因为只要找到一位可以交换这一层的BFS算是结束

Python代码：

def kSimilarity(self, s1: str, s2: str) -> int:
	queue = collections.deque([s1])
	visited = set([s1])
	distance = {s1: 0}
	while queue:
		node = queue.popleft()
		if node == s2:
			return distance[node]
		for i in range(len(node)): # abc, cba
			if node[i] == s2[i]:
				continue
			for j in range(i + 1, len(node)):
				if node[j] == s2[j]:
					continue
				if node[j] == s2[i]:
					ss = node[:i] + node[j] + node[i + 1:j] + node[i] + node[j + 1:]
					if ss in visited:
						continue
					queue.append(ss)
					visited.add(ss)
					distance[ss] = distance[node] + 1
			break # remember
	return -1

算法分析：

时间复杂度为O(解大小)，空间复杂度O(解大小)

LeetCode 839 Similar String Groups

Posted on 2022-02-15 Edited on 2026-06-03 Disqus:

LeetCode

Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y. Also two strings X and Y are similar if they are equal.

For example, "tars" and "rats" are similar (swapping at positions 0 and 2), and "rats" and "arts" are similar, but "star" is not similar to "tars", "rats", or "arts".

Together, these form two connected groups by similarity: {"tars", "rats", "arts"} and {"star"}. Notice that "tars" and "arts" are in the same group even though they are not similar. Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.

We are given a list strs of strings where every string in strs is an anagram of every other string in strs. How many groups are there?

Example 1:

Input: strs = [“tars”,”rats”,”arts”,”star”]
Output: 2

Example 2:

Input: strs = [“omv”,”ovm”]
Output: 1

Constraints:

1 <= strs.length <= 300 1 <= strs[i].length <= 300
strs[i] consists of lowercase letters only. All words in strs have the same length and are anagrams of each other.

题目大意：

单词列表中，可以分成多少组，每组里面的单词互相之间至少有一对可以通过交换一个位置变成另一个单词

解题思路：

典型求连通集个数，类似于Num of island，用BFS。难点在于怎么找到neighbor，用遍历每一个单词的方式

解题步骤：

N/A

注意事项：

难点在于怎么找到neighbor，用遍历每一个单词的方式，判断是否buddyStrings Leetcode 0859

Python代码：

def numSimilarGroups(self, strs: List[str]) -> int:
	if not strs:
		return 0
	visited, groups, word_set = set(), 0, set(strs)
	for s in strs:
		if s in visited:
			continue
		self.bfs(word_set, s, visited)
		groups += 1
	return groups

def bfs(self, word_set, start, visited):
	queue = collections.deque([start])
	visited.add(start)
	while queue:
		node = queue.popleft()
		for s in word_set:
			if s in visited:
				continue
			if node == s or not self.buddyStrings(node, s):
				continue
			queue.append(s)
			visited.add(s)

def buddyStrings(self, s: str, goal: str) -> bool:
	if len(s) != len(goal):
		return False
	if s == goal and len(set(s)) < len(goal):  # any dups
		return True
	diff = [(a, b) for a, b in zip(s, goal) if a != b]
	return True if len(diff) == 2 and diff[0] == diff[1][::-1] else False

算法分析：

时间复杂度为O(nL)，空间复杂度O(n)