详解大厂面试题 - IsUnique

It says "implement an algorithm to determine if all characters in a string are unique " This means that if I have a string for example Paris because all its letters appear only once So all characters are unique So this should be return true For example if I have another string For example Beijing This should be return false Because the letter i appears twice So that's basically what the question means We can approach this problem this way That is we can first put all the characters in a boolean array That means all the characters If it is this kind of as This kind of coding has 128 letters in total Actually before solving this problem let's talk about the encoding of a character So we need to mention the concept called ASCII table That "ask table" means that each character each letter or each symbol corresponds to a number For example the letter a It corresponds to the number 97 If it's the letter k it corresponds to the number 107 There are a total of 128 positions You can see that the order of this number ranges from 0 to 127 which means this number is a digital representation of the character So it's a numerical representation of each letter So our question is to find out whether there are duplicate characters in this string One way to solve it is to say We can create a boolean array What is the length of that boolean array It is set to 128 That means we assign a boolean position for each letter and each symbol That at the beginning all positions were definitely false then we can go through one letter at a time if this letter appears we put it in the position corresponding to this number Change this false to true Give an example For example if we have Beijing then The first letter of Beijing is B What does B correspond to B corresponds to 98 So in this 98th position the boolean array in its 98th position it was originally false right So we'll change this false to true each time like this What would happen if there were duplicate characters For example if it's i which position does i correspond to i corresponds to position 105 So then 105 If we go through it the first time the original value of i is false Right Then we change it to true Then when we encounter i again the second time We are back at position 105 you will find that position 105 it should be false but it has become true by our first it was already changed to true the first time This indicates that it has duplicates So if we go through all of them and each time at each position it is false then it indicates there are no duplicates Okay Let's see how to write this method First let's write the signature framework So this returns a boolean Right Its return type should be boolean For example if it's Beijing If the input is Beijing then the output should be false If the input is Paris then the output should be true So its signature is return boolean Then we call it for example is unique Then there will be an input string First if the length is greater than 128 we set a limit and if it's greater than 128 we just don't consider it anymore Think about it the entire alphabet only has 26 letters If each letter were unique it would definitely not be possible If it were just this one letter Its entire length can't possibly exceed 26 right If it did there would definitely be repeated letters because the entire alphabet only has 26 letters So But we can expand it a bit Expand the entire ask character set that is if it obviously exceeds 128 we will no longer consider it so if it exceeds 128 There will definitely be repeated letters OkayFirst Let's go with this We need what we just mentioned We need a boolean array So we are now building this boolean array We'll call it character set is equal to new boolean Then we set its length to 128 Okay The next step is we will go through this go through this input string and change the corresponding the value in the character set from false to true What needs to be noted is that Because we built a new boolean its default value is false for each position This is a characteristic of that boolean meaning if you don't specifically set its initial value Its initial value is false Okay So how do we get through it How do we get through this string The simplest way is to use a for loop Right So we'll define a for loop We'll start from 0 is less than input length i++ Okay Then we have our for loop Then what We go through them one by one How do we go through them one by one We go through the first one first What is the first character It's input It is a string It has a function called character at i which is the first one for example Beijing the first one is b this equation is actually very interesting you might start to think The character at i returns the character itself So the most common ones are for example define a character new character is equal to this then this returns b but in fact it has another way It's the integer that it can return This integer corresponds to the number on the ask table For example let' s call this value We should find an online Java compiler to see how it works specifically For example if I have a string I have a string the string input is equal to paris then I will output this input For example I can set a value set it as integer value is equal to input character at 0 so this should be output character p then it corresponds to The value in the ask table I will print out this value let's look at p it corresponds to the value that is 112 let's check if it returns 112 Proceed and execute put character a Look where the error is inputsorry input character This is a method so it should use parentheses not square brackets Sook let's execute it again it returns 112 That 112 is actually the letter P in the ASCII table then its number well now that we know this it becomes a bit simpler Let's get the first letter The first letter Its numerical value What do we do after obtaining this value We will look at this character set the character set the corresponding value it is false or true it should all be false at the beginning right If it is true the It already exists So we'll set it first We'll set it to Set it to true first Before true We will check it If If this value In this case If this value is already true then I put it in this if statement if it is already true that means it has already appeared before what does it mean that it has already appeared before It means that this string is no longer unique because it has repeated letters At this point we know the result and can return false Otherwise if there are no duplicates If it is false by itself it will set it to true Okay so if all of these characters and after going through them all it didn't encounter this situation then it means it's unique At this point we can safely return Okay roughly speaking that's the structure Put it into our IDE and run it to see if the result is what we expect Let 's first copy and paste it into IntelliJ I have a type here sorry so it should be character at okay now we first write our main method Okay for example our first one is string input we call it we'll use Beijing Then our second one would be Paris So Paris would return true and Beijing would return false right Then let's check if that's the case We'll start by setting it to static so that we can directly so it can be used directly it's unique We'll first look at input1 then we'll look at input2 ok we'll run this again now okay This result is what we expected The first is false The second is true Okay Then let's talk about its time complexity Its time complexity is big O of n where n is the length of the input string because we need to go through each letter once so if n is larger the time increases The longer the time we need to go through will because if we go through everything again and again then its space complexity is actually a bit tricky you can call it big O of consta So why is it a constant Because that's what you want it to be the most Because we set it that way Its length will not exceed 128 If it's all letters it will not exceed 26 So its largest space is actually the space it uses It's just the positions of 128 letters Right So as long as it doesn't exceed what you can This is what you can argue So its space complexity is actually in a constant situation