LeetCode HOT 100 (02, the oldest string without repeating characters)
Not good enough, hair amount is still much, dental laboratories, can become Buddha.
The importance of algorithm is self-evident. No matter you are a researcher or a popular IT worker recently, you should have certain algorithm ability, which is also a necessary part of the interview. The demonstration of algorithm foundation can often make the interviewer’s eyes shine, which is also an important factor to stand out from most competitors.
However, most people pay more attention to their practical operation ability, focusing on the realization of functions, but ignore the improvement of algorithm ability. Sometimes different algorithms are used to solve the same problem, but the difference in operation efficiency is quite large. After all, we still need to think from the perspective of the customer, and it would be best to bring the user more extreme experience.
All methods are empty, cause and effect is not empty. Taoye was also reluctant to spend too much time on algorithms before, and the algorithm foundation is quite weak. It was not until I entered a new stage of learning that I began to realize the fact of my “food” in the face of various “torture” from my tutor and comparison with others around me.
Speaking of this, my canthus is wet again!!
The topic this time is the third question of LeeTCode’s HOT 100. The difficulty is medium, and it feels a little easier than the second question.
Now, let’s look at this problem.
Title: the oldest string without repeating characters
Given a string, find the length of the smallest string that does not contain repeating characters.
The title Url:https://leetcode.com/problems/longest-substring-without-repeating-characters/
The sample
- Example 1
Input: “abcabcbb” Output: 3 Explanation: Since the oldest string without repeating characters is “ABC”, its length is 3.
- Example 2
Input: “BBBBB” Output: 1 Explanation: Since the oldest string without repeating characters is “b”, its length is 1.
- Example 3
Input: “pwwkew” Output: 3 Explanation: Since the oldest string without repeating characters is “wke”, its length is 3. Note that your answer must be the length of the substring, “pwke” is a subsequence, not a substring.
Train of thought
We need to print the maximum string length without repeating characters. We can use result instead.
Because we need to keep track of whether each character of the input string is repeated in the previously iterated substring, we need a container for temporary storage of characters that have already been iterated.
After analysis, we can find that the temporary container stores two main data, one is the character value, and one is the index value of the character in the input string, and these two attributes have a one-to-one mapping relationship. So it’s not hard to figure out how to replace this container by creating a HashTable or, in Python, using a dict dictionary. We can represent this temporary dictionary container as temp_dict.
In addition, in the process of the input string traversal, also need to use a temporary index, mainly used to record the same as the traverse the current character values on a character indexes, such as: example 1 in the input string for “abcabcbb”, when we traverse to the index to 3, the character of a, and a character in a index of 0. Therefore, when a character iterated over becomes obsolete in temp_dict, we need to change the index of the last character that is the same as the character, from the initial value -1 to 0. We can denote this temporary index as temp_index
So far, the complete algorithm we have obtained is as follows (the algorithm flow and the implementation of the following code) :
- Initialize three variables:
result, temp_dict, temp_index = 0, dict(), -1, the target return values result and temp_dict start with 0 and dict(), and temp_index starts with -1 mainly because we returnThe new resultTime, need withThe result of beforeAnd the maximum length at this point in the traversal, take the maximum of both. - The input string is iterated to determine if the current iterated character is
temp_dict, and the last occurrence index of this character is greater than the temp_INDEX temporary index before the current updateupdateTemporary indextemp_indexAnd temporary dictionariestemp_dict. Otherwise, the first occurrence of the character is added to the temporary dictionarytemp_index, and updates the value of result. - After iterating through the input string, result is returned
Python implementation of this algorithm:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
result, temp_dict, temp_index = 0, dict(), - 1 # Define initial variables
for index, value in enumerate(s): Loop over the input string s
if value in temp_dict and temp_dict[value] > temp_index: Determine whether temp_dict is updated or added
temp_index, temp_dict[value] = temp_dict[value], index Update temp_dcit and temp_index
Add temp_dict and change result
else: temp_dict[value], result = index, max(result, index - temp_index)
return result Return the target result after traversal
Copy the codeC++ implementation of this algorithm (implementation idea is the same as Python) :
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int result = 0, temp_index = -1;
unordered_map<char, int> temp_dict;
for (int index = 0; index < s.size(); index{+ +)
if (temp_dict.count(s[index]) != 0) {
if (temp_dict[s[index]] > temp_index) {
temp_index = temp_dict[s[index]].
temp_dict[s[index]] = index;
}
}else {
temp_dict[s[index]] = index;
result = result > (index - temp_index) ? result : (index - temp_index);
}
}
return result;
}
};
Copy the codeIn addition, the official gives a sliding window implementation, mainly is to find from each character, does not contain repeated characters of the oldest string.
The main core idea of sliding window can refer to the official, or the following three explained ideas, feel very good:
- “LeetCode third topic: their thinking” : https://blog.csdn.net/boling_cavalry/article/details/86563586
- “LeetCode third topic: implement” : https://blog.csdn.net/boling_cavalry/article/details/86654969
- “LeetCode third topic: two optimization” : https://blog.csdn.net/boling_cavalry/article/details/86655675
Recommended reading:
Taoye penetrated into a black platform headquarters, the truth behind it is very afraid of “Big Talk database” -SQL statement execution, what is the bottom of the small action? Over the years, we’ve played Git, Hexo+Github is a deep learning environment based on Ubuntu+Python+Tensorflow+Jupyter Notebook The correct way to open ElasticSearch, Kibana, logStash