Name: 如何解決算法--最長的常用前綴。 (How To Solve Algorithms - Longest Common Prefix)
Uploaded: 2021-01-14T10:22:15.000Z
Duration: 9 min 31 s
Description: 【看影片學英語】數萬部 YouTube 影片，搭配英漢字典即點即查，輕鬆掌握單字發音與用法，長久累積看電影不必再看字幕。

進階形容詞比較級句型

I hope you like solving algorithms, because in today's video, I'm going to be going over the longest common prefix algorithm and showing you the two most common ways to solve it, as well as comparing and contrasting those two ways in order to figure out which one is the most efficient.

情態副詞

Let's get started now, actually, before we get started.

If you enjoy this video, make sure to let me know down in the comments below and tell me what algorithm you want me to cover in the future.

Theo Longest common prefix algorithm is great because it's not necessarily difficult to solve.

But the two common methods just all but are so similar.

Contrast them to figure out why one is better than the other, even though they may look to be exactly the same inefficiency.

Let's take a look at what the algorithm is asking us to do.

It says that we need to write a function to find the longest common prefix string amongst an array of strings that were given, and if there is no prefix, we just returned an empty string, so we look at the first example.

We get three words flower flow and flight and all these start with F L, which is the longest common prefects.

So we return F l down here, we see dog race car in car.

They have nothing in common because it has to be at the beginning of the word has to start there.

And so since there's no common prefix parties which have returned an empty string here and that's all you really need to know about the algorithm to get started.

So let's look at the first most common solution, which is the horizontal method we're gonna take in a ray here of four difference words, we're going to have Apple apply eight and at, and the goal is defined the longest common prefix, which in our case we know is going to be a now with the horizontal method, we're going to take the first and the second word from the rape, and we're going to compare them letter by letter to see where they have similarities and differences.

So we're first gonna look at the A, which is the first letter in both of them, and we see that they both start with a So we continue on to the next letter, which is P They all wear the same Go to the next door, which is p the next one, which is l still the same.

And we finally get to the last word which is e and why?

So we know the longest common prefix in those two is going to be a PPL.

And then we compared that prefix that we determined and compared to the very next word, which in our case is eight.

L eight and we have a that's the same and a p that's the same.

And then the word eight has an E and a PPL has a p, so we know that this difference.

So now we have a P as our longest common prefix on we move on to the very next word, which is at so we compare the and we said that's the same finally compared to paying the tea.

And we said that those were different so that we know that we're done and our longest common prefixes.

Because there's no other elements in the array to look at now.

Using this method will give us the correct answer every single time.

But one thing you may notice is, as in our example, the words of the beginning of the race, such as Apple and Apply have a lot in common.

The prefix is very long, while the words at the end of our ray don't have very much at all incoming with the words of the beginning.

So the prefix is much shorter, and this causes us to accidentally waste time calculating the prefix for the longer words of apple and apply, even though that prefix does not apply to the later words in our ray.

So we're wasting a few computations doing that.

So the next month that we could take a look at which avoids that problem is called the vertical method, and the way the vertical method works is instead of comparing two words at a time, you compare all the words at once, but you compare them one letter at a time.

So, for example, we take the very first character from all of our different words, which in our case is a for Apple A for apply a for a pin, A Fred and we say, is each one of these characters exactly the same.

If so, move on to the next character in every single one of our words.

And in our case we see that the P and the pier the same for AP won't apply.

We see that the P and appear the same for eight and app apply.

But when we get down to eight and at we see that the P and the tear difference.

So we know right there and then that our longest prefixes A.

And we can stop what I have been to go further into an apple and apply in eight.

We could just stop right there at the A Now.

One thing to note is that these algorithms have exactly the same space, complex city and time complexity, which in theory would make you think that they're both equally is valid to the solution.

But one thing to note is that the vertical slice method has a better time to solve the problem.

In the best case scenario in the horizontal method, let's just take a look at a really contrived example where you have an array of 1000 different words, and all of the words are exactly the same.

Except for the very last word is completely different.

Let's say we have 1000 words that are apple and the very last word is tiger.

So, using the horizontal method, you have to go through each word in the array Apple, apple, apple up.

We get about 999 times before you finally get down to Tiger and you realize, OK, we can quit.

There's no common prefix, but with the vertical slice method, you go through the first letter of every single word, all the A's for apples.

But you only have to go through that first letter, and then you get down to Tiger and you realize hope this is completely different.

Weaken kitted out immediately without having to do all of the rest of the letters of apple.

For all the other words, this is where the vertical slice mended is much quicker to solve the algorithm in these certain scenarios.

Now let's take a look at how we decode the vertical slice met that to solve this problem in Java script.

Now, before we start writing the real code, that's right.

A little bit of pseudo code to understand what we want to do.

The first thing we need to do is we just wanted to find a prefix variable, which we're gonna default to an empty string.

Then what we want to do is you wanna live through all of the characters.

So we're gonna say, Luke their characters and this is just going to give us the character as well as the index for whichever character were already on then inside of that loop.

What we want to do is we want to look through all the strings.

This is going to return to us in just a single string that we can use.

Then now, once we have all of our strings inside of a loop as walls over characters and Luke, we need to do the comparison to make sure that our strings all have the same character at the beginning.

So we can do in here is we can just say that we want to compare.

So if as tr of index so essentially whichever characters at that specific index inside of our string is equal to our character.

Then we know that everything is good and we can continue.

But if for some reason, these air not equal so we'll say not equal.

What we want to do inside of this scenario is we want to actually just exit out and return our prefix.

And this is because if our strings do not match, our characters do not match.

We now no longer have a prefix that could be any longer than our current prefects, and we immediately need to return our prefix that we have.

But if for some reason we get outside of this entire loop so we're down here outside of our entire loop for all of our strings, we know that they all match the prefix so we can add that character to our prefix.

It is going to be equal to our prefix plus our character and they can continue looping through like that until we get to the very end.

And if we get out of sight of all of our loops which want to return our prefix.

I know the pseudo code right here is going to give us everything we need to do in order to write our real code.

First thing we can do is actually find our prefix, so we could just say prefix is going to be equal to an empty string.

And now, before we jump into looking through all of our different characters in a raise, we want to check to make sure we actually got past an array with actual items in it.

So we're going to say here, that is our strings dot length Is it going to be equal to zero?

That means we have absolutely nothing in our way and can just return our prefix, which is an empty string, which means that there's no common prefix because there's no arrays toe loop there.

Now we want to start looking to the characters and to do this but we need to do is just create a for loop.

To start with, we're gonna make sure I is less than our strings zero, which means we're just gonna get the first string in our ray of all of our strings, we want to check to make sure it's less than the length of that.

And we're gonna increment this by one as we d'oh!

So, essentially, what this poor Luke is going to do is look through all the different characters of our very first string.

And the reason we only need to look over our first string is if we somehow run out of characters on our first string.

We know that that's the longest common prefix because we can't go any further since that the longest are shorter string is.

So instead of here, we can actually set our character.

So we're going to say our character is going to be equal to STRS of Zero again and we just want to get the ice character.

So just like this, this is going to give us the eye character.

So at the very beginning is gonna give us our first character, second character, third character, and so on.

Now we can do another four Luke instead of here.

What is going to create a variable called J Clips J.

We're gonna default That 20 We're going to say when Jay is less than the length of our strings, right, Because we want to live through all of our different strings and we're going to incriminate J now that we have that loop complete, let's work on our comparison.

So we just in here are going to take our STRS.

We want to get the Jade element, which is the string that were on inside of this loop.