preface

For the algorithm, I think, some are just their own hard, private thinking, drawing more, more understanding.

There is no best way, nor the fastest way, there is only their own exploration and constantly forward, attached to the previous brush notes:

  • Algorithm Notes | LeetCode 349. Intersection of two arrays – easy

Think more, draw more, practice more, think more, understand more, share more, do not panic, do not be afraid, step by step forward.

Come on ~

GitHub address:

  • Github.com/HLQ-Struggl…

14. Longest public prefix

Write a function to find the longest public prefix in an array of strings.

Returns the empty string “” if no public prefix exists.

Example 1:

Input: ["flower","flow","flight"] Output: "fl"Copy the code

Example 2:

Input: ["dog","racecar","car"] Output: "" Explanation: The input does not have a common prefix.Copy the code

Description:

  • All inputs contain only lowercase letters A-z.

Violent solution number one

Enter the sketch and say the idea:

  • Basic check: If the input array is empty, return directly. If there is only one input array, return directly.
  • Char = char; char = char; char = char; char = char; Return when the base is empty.

First of all, the longest common, which is to start with each item in the array and stop if it’s different. This is where I started the conversation.

Here’s the code:

fun longestCommonPrefix(strs: Array<String>): String { var resultStr = "" if (strs.isEmpty()) { return resultStr } if (strs.size == 1) { return strs[0] } resultStr = strs[0] for(str in strs){ var j = 0 while (j < resultStr.length && j < str.length){ if(str.toCharArray()[j] ! = resultStr.toCharArray()[j]){ break } j++ } resultStr = resultStr.substring(0,j) if(resultStr.isEmpty()){ break } } return resultStr }Copy the code

Consumption:

Violent solution number two

During Debug, you suddenly discover that the loop alignment for the first solution starts from scratch. This should start with the first digit of the array, because the first digit of the array is used as the base for comparison.

fun longestCommonPrefix2(strs: Array<String>): String { var resultStr = "" if (strs.isEmpty()) { return resultStr } if (strs.size == 1) { return strs[0] } resultStr = strs[0] for(i in 1 until strs.size){ var j = 0 while (j < resultStr.length && j < strs[i].length){ if(strs[i].toCharArray()[j] ! = resultStr.toCharArray()[j]){ break } j++ } resultStr = resultStr.substring(0,j) if(resultStr.isEmpty()){ break } } return resultStr }Copy the code

Consumption:

Violent solution number three

Why do I have to toCharArray() every time? Can’t I just take the corresponding value?

Modify the code again:

class Solution { fun longestCommonPrefix(strs: Array<String>): String { var resultStr = "" if (strs.isEmpty()) { return resultStr } if (strs.size == 1) { return strs[0] } var len = strs.size Arrays.sort(strs) for (i in strs[0].indices){ if(strs[len-1][i] == strs[0][i]){ resultStr += strs[0][i] }else{  break } } return resultStr } }Copy the code

Consumption:

Let’s learn the big guy solution, the sorting method

After thinking and debugging, the train of thought is as follows:

  • Basic check is the same as above, no longer mentioned;
  • Sort the array, comparing the first to the last. I guess it’s based on sorting the array.

Here’s a quick example:

The array is provided as follows:

  • {“flower”, “flow”, “flight”}

After sorting, it becomes:

  • {“flight”, “flow”, “flower”}

You can then compare the first and last array.

Finally, the longest public prefix is:

  • fl

Post the code section:

fun longestCommonPrefix3(strs: Array<String>): String { var resultStr = "" if (strs.isEmpty()) { return resultStr } if (strs.size == 1) { return strs[0] } val len = strs.size Arrays.sort(strs) for (i in strs[0].indices){ if(strs[len-1][i] == strs[0][i]){ resultStr += strs[0][i] }else{  break } } return resultStr }Copy the code

Consumption:

This solution is a little confusing

In LeetCode, the optimal solution tells me something like this. But after the actual submission, no one found the best.

And the LeetCode of the same code section submitted twice, time and consumption is not the same, very strange.

Let me just say a little bit about the solution.

  • The same check, but another array element nulled;
  • First get the shortest length of the array;
  • Then get the same index;
  • Finally intercept back

Here’s a quick example:

Given the following array:

  • {“flower”, “flow”, “flight”}

Basic verification is ignored here.

Gets the shortest length of the supplied array, which is the flow 4 bits. We then compare the first item in the array, and the index of the same item is 1, which is fl. Return clipping the index.

The following code is attached:

fun longestCommonPrefix4(strs: Array<String>): String { if (strs.isEmpty()) { return "" } if (strs.size == 1) { return if(strs[0].isEmpty()) "" else strs[0] } // Var min = int.max_value for(STR in STRS){if(min > str.length){min = str.length}} var isl = true var index = 0 while (index < min){ for(i in strs.indices){ if(strs[0][index] ! = strs[i][index]){ isl = false break } } if(! isl){ break } index++ } return strs[0].substring(0,index) }Copy the code

Consumption time:

In order to avoid the big guy spray me, here released this solution address:

End

The algorithm thing, really, a lot of practice, a lot of drawing, a lot of debugging, slowly transform your own stuff.

This idea is really quite good, at least the present oneself seems to feel so a little bit.

Another bit of their own caution is:

  • Don’t go up and get the best solution. It is impossible without a certain amount of accumulation. There is no such thing as talent. Start with violence and work your way up. Look at older code, learn more, understand people’s thinking.

In addition, the essence of technological progress is sharing, and the exchange of ideas can lead to a variety of wonderful ideas.

Come on together ~

Welcome big guy to give directions ~

The resources

  • Longest Public Prefix (14)
  • Novel sorting algorithm