LeetCode Notes: Reverse String

#leetcode

Question

Write a function that reverses a string. The input string is given as an array of characters s.

Example 1:

Input: s = ["h","e","l","l","o"]

Output: ["o","l","l","e","h"]

Example 2:

Input: s = ["H","a","n","n","a","h"]

Output: ["h","a","n","n","a","H"]

Constraints:

  • 1 <= s.length <= 105
  • s[i] is a printable ascii character.

Follow up: Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

ACSII code printable characters

DecimalSymbolInterpretationDecimalSymbolInterpretation
32space80PCapital letter P
33!exclamation mark81QCapital letter Q
34"Double quotation marks82RCapital letter R
35#Pound sign83SCapital letter S
36$Dollar sign84TCapital letter T
37%Percent sign85UUppercase letter U
38&and86VCapital letter V
39'Single quotation mark87WCapital letter W
40(Left bracket88XCapital letter X
41)Close parenthesis89YCapital letter Y
42*Asterisk90ZCapital letter Z
43+Plus Sign91[Left bracket
44,Comma92\ Backslash
45-hyphen or minus sign93]right square bracket
46.period or decimal point94^diacritics
47/slash95_Underscore
480096`Accents
491197alowercase a
502298blowercase letter b
513399clowercase letter c
5244100dlowercase letter d
5355101elowercase letter e
5466102fLowercase letter f
5577103glowercase letter g
5688104hlowercase letter h
5799105ilowercase i
58:colon106jlowercase letter j
59;semicolon107klowercase letter k
60<Less than108llowercase letter l
61=equal sign109mLowercase letter m
62>greater than110nlowercase letter n
63?question mark111olowercase letter o
64@electronics Mail symbol112plowercase letter p
65AUppercase letter A113qLowercase letter q
66BUppercase letter B114rLowercase letter r
67CCapital letter C115slowercase letter s
68Duppercase letter D116tlowercase letter t
69ECapital letter E117uLowercase letter u
70FCapital letter F118vLowercase letter v
71GUppercase letter G119wlowercase letter w
72Huppercase letter H120xlowercase letter x
73IUppercase letter I121yLowercase letter y
74JUppercase letter J122zLowercase letter z
75KCapital letter K123{Left brace
76LCapital letter L124|Vertical line
77MCapital letter M125}right brace
78NCapital letter N126~tilde
79OCapital letter O127Delete

Solution

Analysis:

  1. First add an order mark for each character
  2. Sort the array in reverse order according to the order of the identification to achieve the reverse effect
  3. Extract the key character in the inverted array and reset the character

Note:

The requirement in the question is the printable characters in the ASCII code table. Based on this requirement, if the order mark is added in the first step, use ['0-a','1-b','2-c'] The way of dividing characters to sort is not rigorous enough.

Code:

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
    /**
     * Add an order mark for each character
     *
     * ['a','b','c']
     *
     * =>
     *
     * [
     *  {index:0,str:'a'},
     *  {index:1,str:'b'},
     *  {index:2,str:'c'},
     *]
     */
    s.map((item,index)=>{
        return {
            index:index,
            str:item
        }
    })
    /**
     * Reverse order
     *
     * [
     *  {index:0,str:'a'},
     *  {index:1,str:'b'},
     *  {index:2,str:'c'},
     *]
     *
     * =>
     *
     * [
     *  {index:2,str:'c'},
     *  {index:1,str:'b'},
     *  {index:0,str:'a'},
     *]
     */
    .sort((a,b)=>{
        
        return b.index-a.index

    })
    /**
     * Restore
     *
     * [
     *  {index:2,str:'c'},
     *  {index:1,str:'b'},
     *  {index:0,str:'a'},
     *]
     *
     * =>
     *
     * [ 'c', 'b', 'a']
     */
    .forEach((item,index,arr)=>{
         s[index] = item.str
    })
};

Reference

Comments