KK's blog

LeetCode

<div>

This is an interactive problem.

You are given an array of unique strings wordlist where wordlist[i] is 6 letters long, and one word in this list is chosen as secret.

You may call Master.guess(word) to guess a word. The guessed word should have type string and must be from the original list with 6 lowercase letters.

This function returns an integer type, representing the number of exact matches (value and position) of your guess to the secret word. Also, if your guess is not in the given wordlist, it will return -1 instead.

For each test case, you have exactly 10 guesses to guess the word. At the end of any number of calls, if you have made 10 or fewer calls to Master.guess and at least one of these guesses was secret, then you pass the test case.

Example 1:

<pre>Input: secret = "acckzz", wordlist = ["acckzz","ccbazz","eiowzz","abcczz"], numguesses = 10 Output: You guessed the secret word correctly. Explanation: master.guess("aaaaaa") returns -1, because "aaaaaa" is not in wordlist. master.guess("acckzz") returns 6, because "acckzz" is secret and has all 6 matches. master.guess("ccbazz") returns 3, because "ccbazz" has 3 matches. master.guess("eiowzz") returns 2, because "eiowzz" has 2 matches. master.guess("abcczz") returns 4, because "abcczz" has 4 matches. We made 5 calls to master.guess and one of them was the secret, so we pass the test case. </pre>

Example 2:

<pre>Input: secret = "hamada", wordlist = ["hamada","khaled"], numguesses = 10 Output: You guessed the secret word correctly. </pre>

Constraints:

• 1 <= wordlist.length <= 100
• wordlist[i].length == 6
• wordlist[i] consist of lowercase English letters.
• All the strings of wordlist are unique.
• secret exists in wordlist.
• numguesses == 10

</div>

题目大意：

给定单词列表，每个单词长度为6， 其中一个为答案，每次猜一个单词。给一个API会告诉你猜的单词有多少位命中(位置,数值), 求是否可以10次内猜对

暴力法解题思路：

较直观的解法是抽第一个单词出来，然后call API, 然后再filter wordlist使得新的单词列表里的单词的命中位数也是一样的。每轮缩少范围。

解题步骤：

N/A

注意事项：

Python代码：

1
2
3
4
5
6
7
8

def findSecretWord2(self, wordlist, master):
	for i in range(10):
		guess = wordlist[0]
		res = master.guess(guess)
		wordlist = [w for w in wordlist if self.match(w, guess) == res]

def match(self, w1, w2):
	return sum(i == j for i, j in zip(w1, w2))

算法分析：

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

统计频率算法II解题思路(推荐)：

上述方法跟单词个数有关，如果很多的话，就会超过10次。考虑单词长度为6，而可以猜10次。考虑用26字母存储法，也就是统计频率。统计每位的频率，然后将频率作为这一位的分数，求每个单词的总分。 一定要选择单词列表中的某个单词去猜，如果不在列表中返回为-1，这个信息没有任何作用。 选择总分最高的去猜，原理是它最具代表性，这样可以快速排除很多单词，有点类似于二分法。反之，若用频率低的单词，也就只能排除一个单词。

Python代码：

1
2
3
4
5
6
7
8
9

def findSecretWord(self, wordlist, master):
	for _ in range(10):
		char_to_count = [collections.Counter(w[i] for w in wordlist) for i in range(6)]
		guess = max(wordlist, key=lambda w: sum(char_to_count[i][char] for i, char in enumerate(w)))
		res = master.guess(guess)
		wordlist = [w for w in wordlist if self.match(w, guess) == res]

def match(self, w1, w2):
	return sum(i == j for i, j in zip(w1, w2))

算法分析：

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

LeetCode

<div>

You are asked to design a file system that allows you to create new paths and associate them with different values.

The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, "/leetcode" and "/leetcode/problems" are valid paths while an empty string "" and "/" are not.

Implement the FileSystem class:

• bool createPath(string path, int value) Creates a new path and associates a value to it if possible and returns true. Returns false if the path already exists or its parent path doesn't exist.
• int get(string path) Returns the value associated with path or returns -1 if the path doesn't exist.

Example 1:

<pre>Input: ["FileSystem","createPath","get"] [[],["/a",1],["/a"]] Output: [null,true,1] Explanation: FileSystem fileSystem = new FileSystem();

fileSystem.createPath("/a", 1); // return true fileSystem.get("/a"); // return 1 </pre>

Example 2:

<pre>Input: ["FileSystem","createPath","createPath","get","createPath","get"] [[],["/leet",1],["/leet/code",2],["/leet/code"],["/c/d",1],["/c"]] Output: [null,true,true,2,false,-1] Explanation: FileSystem fileSystem = new FileSystem();

fileSystem.createPath("/leet", 1); // return true fileSystem.createPath("/leet/code", 2); // return true fileSystem.get("/leet/code"); // return 2 fileSystem.createPath("/c/d", 1); // return false because the parent path "/c" doesn't exist. fileSystem.get("/c"); // return -1 because this path doesn't exist. </pre>

Constraints:

• The number of calls to the two functions is less than or equal to 10<sup>4</sup> in total.
• 2 <= path.length <= 100
• 1 <= value <= 10<sup>9</sup>

</div>

题目大意：

设计文件系统，支持创建路径，路径含key, value

Trie解题思路：

用Trie, is_end变成key, value

解题步骤：

N/A

注意事项：

1. 遍历用1开始，因为首个/前面是空字符串

Python代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class FileSystem(TestCases):

    def __init__(self):
        self.head = TrieNode('')

    def createPath(self, path: str, value: int) -> bool:
        segments = path.split('/')

        it = self.head
        for i in range(1, len(segments)):
            segment = segments[i]
            if segment not in it.children:
                if i == len(segments) - 1: # match all the previous segments
                    it.children[segment] = TrieNode(segment)
                else:
                    return False
            it = it.children[segment]
        if it.value != -1: # exists
            return False
        it.value = value
        return True

    def get(self, path: str) -> int:
        segments = path.split('/')

        it = self.head
        for i in range(1, len(segments)):
            segment = segments[i]
            if segment not in it.children:
                return -1
            it = it.children[segment]
        return it.value

class TrieNode:

    def __init__(self, name):
        self.children = collections.defaultdict(TrieNode)  # {}
        self.name = name
        self.value = -1

算法分析：

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

算法II HashMap解题思路：

用前缀法

Python代码：

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

class FileSystem2(TestCases):

    def __init__(self):
        self.path_to_val = defaultdict()

    def createPath(self, path: str, value: int) -> bool:

        if path == "/" or len(path) == 0 or path in self.path_to_val:
            return False

        # search from the right
        parent = path[:path.rfind('/')]
        if len(parent) > 1 and parent not in self.path_to_val:
            return False

        self.path_to_val[path] = value
        return True

    def get(self, path: str) -> int:
        return self.path_to_val.get(path, -1)

算法分析：

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

LeetCode

<div>

You are given two strings of the same length s and t. In one step you can choose any character of t and replace it with another character.

Return the minimum number of steps to make t an anagram of s.

An Anagram of a string is a string that contains the same characters with a different (or the same) ordering.

Example 1:

<pre>Input: s = "bab", t = "aba" Output: 1 Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s. </pre>

Example 2:

<pre>Input: s = "leetcode", t = "practice" Output: 5 Explanation: Replace 'p', 'r', 'a', 'i' and 'c' from t with proper characters to make t anagram of s. </pre>

Example 3:

<pre>Input: s = "anagram", t = "mangaar" Output: 0 Explanation: "anagram" and "mangaar" are anagrams. </pre>

Constraints:

• 1 <= s.length <= 5 * 10<sup>4</sup>
• s.length == t.length
• s and t consist of lowercase English letters only.

</div>

题目大意：

通过替换字母使得两字符为同位词Anagram

解题思路：

统计某一个词的词频，遍历另一个单词，减去词频，若不够减(小于0)，就加步数

解题步骤：

N/A

注意事项：

Python代码：

1
2
3
4
5
6
7
8
9

def minSteps(self, s: str, t: str) -> int:
	char_to_count_t = collections.Counter(t)
	steps = 0
	for char in s:
		if char in char_to_count_t and char_to_count_t[char] > 0:
			char_to_count_t[char] -= 1
		else:
			steps += 1
	return steps

算法分析：

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

LeetCode

<div>

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:

<pre>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". </pre>

Example 2:

<pre>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". </pre>

Constraints:

• 1 <= s.length, p.length <= 3 * 10<sup>4</sup>
• s and p consist of lowercase English letters.

</div>

题目大意：

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

解题思路：

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

解题步骤：

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

注意事项：

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

<div>

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:

<pre>Input: s1 = "ab", s2 = "eidbaooo" Output: true Explanation: s2 contains one permutation of s1 ("ba"). </pre>

Example 2:

<pre>Input: s1 = "ab", s2 = "eidboaoo" Output: false </pre>

Constraints:

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

</div>

题目大意：

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

解题思路：

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

解题步骤：

N/A

注意事项：

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

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)