1. Longest public prefix

Finds the longest public prefix in an array of strings. Returns the empty string “” if no public prefix exists.

STRS = [“flower”,”flow”,”flight”]

Output: “fl”

Find the longest public prefix for all strings, then we can use any string STR to do the first comparison.

Then compare it to the following string using STR as the standard. The new common prefix str1, then STR = str1. Let’s go ahead and compare.

Here’s the code:

var longestCommonPrefix = function(strs) {
  if (strs.length === 0) return ''
  let i = 0
  let str = strs[0]
  let index = 1
  while (index < strs.length) {
    while (str[i] === strs[index][i] && i < str.length) {
      i++
    }
    str = str.substring(0, i)
    i = 0
    index++
  }
  return str
}
Copy the code
2. The longest substring

Given a string s, find the longest substring in s.

Anaphora substring: read from front to back === read from back to front

Enter: s = “babad”

Output: “the bab”

Explanation: “ABA” is also a suitable answer to the question.

Resolution:

Center development method:

If you are interested, you can also take a look at dynamic programming and horse-drawn cart algorithms

Take a certain point as the center and expand to both sides. If a is taken as the origin and bab is expanded on both sides, the rule of the loop substring is satisfied, then continue to expand to both sides. If bac is matched, then there is no need to expand to both sides, because the string that matches is definitely not a callback substring.

Another thing to consider is that it is not necessary for the subroutines to be odd, but they may be even. So another possibility is to start with two origins and then expand on both sides.

Time complexity: O(n^2) where n is the length of the string. There are n and n-1 palindromic centers of length 1 and 2 respectively, and each palindromic center will expand outwardly at most O(n) times.

Space complexity: O(1).

Here is the reference code:

var longestPalindrome = function(s) { if (s.length <= 1) return s let start = 0 let end = 0 for (let i = 0; i < s.length; I ++) {let len1 = judgeIs(s, I, I) // let len2 = judgeIs(s, I, I + 1) // Let len2 = judgeIs(s, I, I + 1) // Let len = math.max (len1, len1) len2) if (len > end - start) { start = i - (len - 1) / 2 end = i + len / 2 } } return s.substring(Math.round(start), end + 1) } var judgeIs = function (s, left, right) { let L = left let R = right while (L >= 0 && R < s.length && s.charAt(L) === s.charAt(R)) { L-- R++ } return R -  L - 1 }Copy the code
3. String matching algorithm: KMP

Knuth-morris-pratt (KMP) algorithm is an improved string matching algorithm. Its core is to reduce the matching times of pattern string and main string as much as possible to achieve the purpose of fast matching by using the information after the failure of matching. Its time is order m plus n.

Reference links:

Leetcode-cn.com/leetbook/re… www.zhihu.com/question/21…

To understand the KMP algorithm, you need to understand one of the core things: Partial Match tables. If you understand the table PMT, you’ll get the idea.

The value in PMT is the length of the longest element in the intersection of the prefix and suffix sets of strings.

Prefix: string: the prefix of ABC is {a, ab}. This set is the set of prefixes for the string ABC

Suffix: string: the suffix for ABC is {BC, a} this set is the set of suffixes for the string ABC

Intersection of two sets: {a}, then the longest element is a and the length is 1

For the string “abababca”, its PMT is as follows:

char: a b a b a b c a
index 0 1 2 3 4 5 6 7
PMT 0 0 1 2 3 4 0 1

And then we move the value array one bit to the right, and then we fill in -1 to form the next array

char: a b a b a b c a
index 0 1 2 3 4 5 6 7
PMT 0 0 1 2 3 4 0 1
next – 1 0 0 1 2 3 4 0

Here is a code reference to get the next array:

var getNext = function (needle) {
    let i = 0
    let j = -1
    let next = []
    next[0] = -1
    while (i < needle.length) {
        if (j === -1 || needle[i] === needle[j]) {
            i++
            j++
            next[i] = j
        } else {
            j = next[j]
        }
    }
    return next
}
Copy the code

Overall code:

var strStr = function(haystack, needle) {
    if (needle === '') return 0
    let i = 0
    let j = 0
    let next = getNext(needle)
    while(i < haystack.length && j < needle.length) {
        if (j === -1 || haystack.charAt(i) === needle.charAt(j)) {
            if(j === needle.length - 1) return (i - needle.length + 1)
            i++
            j++
        } else {
            j = next[j]
        }
    }
    return -1
}
var getNext = function (needle) {
    let i = 0
    let j = -1
    let next = []
    next[0] = -1
    while (i < needle.length) {
        if (j === -1 || needle[i] === needle[j]) {
            i++
            j++
            next[i] = j
        } else {
            j = next[j]
        }
    }
    return next
}
Copy the code
4. Flip the word in the string

Given a string, you need to reverse the character order of each word in the string, while still preserving the Spaces and the original order of the words.

Enter: “Let’s take LeetCode Contest”

“S ‘tel ekat edoCteeL tsetnoc”

Resolution:

This problem can be repeated from the beginning, with a space as a word boundary to do the flip

You can also convert the string to an array and flip the individual members

Here is the reference code:

var reverseWords = function(s) {
    s = s.split(' ')
    s = s.map(i => {
        return i.split('').reverse().join('')
    })
    return s.join(' ')
}
Copy the code