1. Hump conversion (regular)

The hump is named camelCase and the dash is named Kebab-case

(1) convert ‘getElementById’ to ‘get-elementby-id’

const getKebabCase = function(str) {
  // str.replace does not change the original string, so return is required
  return str.replace(/[A-Z]/g.(i) = > The '-' + i.toLowerCase());
}
Copy the code

(2) convert ‘get-element-by-id’ to ‘getElementById’

const getCamelCase = function(str) {
  // /w matches any letters, digits, and underscores
  // $0,$1 matches the NTH group
  return str.replace(/-(\w)/g.($0, $1) = > $1.toUpperCase());
}
Copy the code

2. The oldest string without repeating characters (3)

Sliding window O(n) :

Use two Pointers lt, RT represents the left and right boundary of the sliding window, map structure is used to store the string in the sliding window, key represents the character, value represents the index of the character.

Whenever the right pointer is moved to the right, it will first determine whether the map structure contains the character, and then update the left pointer. Both map and RES need to be updated regardless of whether the character is contained.

const longestSubString = function(str) {
  let lt = rt = res = 0;
  const map = new Map(a);for(; rt < str.length; rt++) {
    if (map.has(str[rt])) {  // Slide window has repeated characters, right shift lt
      lt = Math.max(lt, map.get(str[rt]) + 1);  // Max must be used to keep lt from backsliding
    }

    map.set(str[rt], rt);  // Key is the character, value is the character index, convenient lt change
    res = Math.max(res, rt - lt + 1);
  }
  return res;
}
Copy the code

3. Comparison of version Numbers (165)

Spilt + parseInt O (m + n) :

const compareVersion = function(version1, version2) {
  const v1 = version1.split('. '),
        v2 = version2.split('. ');
  // The traversal length takes the maximum length of the two version numbers
  for (let i = 0; i < v1.length || i < v2.length; i++) {
    let num1 = i < v1.length ? parseInt(v1[i]) : 0,
        num2 = i < v2.length ? parseInt(v2[i]) : 0;
    if (num1 > num2)  return 1;
    if (num1 < num2)  return -1;
  }
  return 0;
}
Copy the code

4. String Addition (415)

General idea O(Max (m, n)) : simulate vertical addition, define two Pointers P1 and P2 to point to the end of two numbers respectively, define variable add to maintain the current carry, in addition, complement 0 for the short number of digits.

Optimization: Optimization of complement 0 operations, such as adding a long and a short character, can only add the following bits.

const addStrings = function(s1, s2) {
  let p1 = s1.length - 1, p2 = s2.length - 1;    // The p pointer initially points to the ones bit
  let add = 0, res = [];   / / carry
    
  while (p1 >= 0 || p2 >= 0 || add) {   //@ carry add is not 0
    // Because strings cannot be modified directly, only characters can be extracted for assignment
    let ch1 = s1[p1] ? s1[p1] : '0',
        ch2 = s2[p2] ? s2[p2] : '0';
    let sum = parseInt(ch1) + parseInt(ch2) + add;
    add = parseInt(sum / 10);
    res.push(sum % 10);
    p1 -= 1;
    p2 -= 1;
  }
  return res.reverse().join(' ');  //@ reverse
}
Copy the code

5. Valid parentheses (20)

Stack O (n) :

Iterating through the string s, when it encounters an open parenthesis, when it encounters a close parenthesis, if the stack is empty, or if the character is not equal to the top of the stack, it is definitely not a valid parenthesis, and if it is equal to the top of the stack, it is off the stack. Finally, a Boolean value is returned based on the stack size.

const isValid = function(s) { 
  if (s.length % 2= = =1) return false;  // The length is odd, invalid parentheses
  const map = new Map([[') '.'('],
    ['} '.'{'],
    ['] '.'[']]);const stack = [];
  for (let ch of s) {  // More efficient than the for loop
    if (map.has(ch)) {  / / right parenthesis
      // If stack is empty, or not equal to the top element of the stack
      if(! stack.length || stack[stack.length -1] !== map.get(ch)) {
        return false;
      } 
      stack.pop();
    } else {  / / left parenthesisstack.push(ch); }}return! stack.length;//@ contains both cases, or two ifs instead
}
Copy the code

6. Longest loop substring (5)

Center diffusion O(n^2) :

Space complexity O(1)

const longetSubString = function(s) {
  if (s.length < 2) return s;
  let res = ' ';
  // Iterate over the string to extract the palindrome string for each character
  function sliceString(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left -= 1;  // Expand the scope synchronously
      right += 1;
    }
    Left + 1 and right-1 are left + 1 and right-1
    let len = (right - 1) - (left + 1) + 1;
    res = len > res.length ? s.slice(left + 1, right)  : res;  // Slice extraction does not contain the right character
  }

  for (let i = 0; i < s.length; i++)  {
    // Assume an odd number of palindromes
    sliceString(i, i);
    // Assume an even number of palindromes
    if (i + 1 < s.length) {
      sliceString(i, i + 1); }}return res;
}
Copy the code

7. Longest Public Prefix (14)

Initialize the value of the longest public prefix s as the first string, iterate through the following strings, and compare the result to the longest public prefix. If s is empty during the search, return “” directly.

Time complexity O(s).

const longestCommonPrefix = function(strs) {
  if (strs.length === 1)  return "";
  let s = strs[0];

  for (let i = 1; i < strs.length; i++) {
    let j = 0;
    for (; j < Math.min(s.length, strs[i].length); j++) {
      if(s[j] ! == strs[i][j]) {// Characters are not equal
        break; }}// If it is placed in the second loop, if the length of one side is 1, it will not enter the if judgment once, so it will return s directly
    s = s.substr(0, j);  // The @ position is placed in the layer 2 for loop
    if(! s)return s;  
  }
  return s;
}
Copy the code

8. Parenthesis generation (22)

DFS:

First, a valid parenthesis sequence must satisfy two conditions :(1) the number of left and right parentheses is equal; (2) The number of open parentheses in any prefix >= the number of close parentheses, so that each close parentheses can be guaranteed to find a matching open parentheses.

Design idea: the problem of generating n pairs of legal parenthesis sequences is transformed into the problem of what to fill in each bit of the sequence. Because in a legal sequence of parentheses, the number of open parentheses in any prefix must be greater than or equal to the number of close parentheses, so (1) if the number of open parentheses is not greater than or equal to n, we can put an open parenthesis and (2) if the number of close parentheses is less than the number of open parentheses, we can put a close parenthesis.

Function DFS (n, lc, rc, STR). 1. The initial number of open parentheses lc and close parentheses RC is 0. 2. If lc is less than the parenthesis logarithm n, concatenate the left parenthesis after the current legal sequence STR. 3. If the number of close parentheses is less than the number of open parentheses, concatenate the close parentheses after the current sequence STR. 4. Add the current legal sequence STR to the result array res when lc and rc are equal to n.

Time complexity: Classical Catalan number problems, O(CN-2n), understood in conjunction with graphs.

const res = [];  // Global variables
function dfs(n, lc, rc, str) {
  if (lc == n && rc == n) {
    res.push(str);
  }
  else {   // if (" if ", "if")
    if (lc < n) dfs(n, lc + 1, rc, str + "(");
    if (rc < n && lc > rc)  dfs(n, lc, rc + 1, str +")"); }}const generateValidString = function(n) {
  dfs(n, 0.0."");
  return res;
}
Copy the code