Press "Enter" to skip to content

Posts published in “String Manipulation”

LeetCode 763. Partition Labels (javascript)

By stone on March 27, 2021

A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

Note:

  • S will have length in range [1, 500].
  • S will consist of lowercase English letters ('a' to 'z') only.

Idea:

  • Create hash table to track the last index of the letter
  • use start and end variable to decide the partition letters
  • when end reach to the last index of the letter :
    • store the length of the partition letters (end – start + 1)
    • reset start => end + 1

Solution:

/**
 * @param {string} S
 * @return {number[]}
 */
var partitionLabels = function(S) {
    let last_index = new Map();
    for (let i = 0; i < S.length; i++) {
        last_index.set(S[i],  i);
    }
    let res = [];
    let start = 0;
    let end = 0;
    for (let i = 0; i < S.length; i++) {
        end = Math.max(end, last_index.get(S[i]));
        if (i === end) {
            res.push(end - start + 1);
            start = end + 1;
        }
    }
    return res;
};

LeetCode 14. Longest Common Prefix (javascript)

By stone on March 27, 2021

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lower-case English letters.

Idea:

  • Use first string for comparison
  • loop through each string:
    • store the common letter if match
    • or return the answer if no match

Solution:

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) return "";
    let ans = "";
    for (let i = 0; i < strs[0].length; i++) {
        for (let s of strs) {
            if (s.length <= i || s[i] !== strs[0][i]) return ans;
        }   
        ans += strs[0][i];
    }
        
    return ans;
};

LeetCode 6. ZigZag Conversion (javascript)

By stone on March 27, 2021

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Example 3:

Input: s = "A", numRows = 1
Output: "A"

Constraints:

  • 1 <= s.length <= 1000
  • s consists of English letters (lower-case and upper-case), ',' and '.'.
  • 1 <= numRows <= 1000

Idea:

  • Treat this as an elevator
  • The letter trend is from the top to the bottom, and then from the bottom to the top as the elevator, so only need to build n(numRows) level strings elevator, each string represents a layer(level)
  • every time to visit a layer(level) while loop through the String s, store that letter into visiting layer(level)
  • merge all the layers to get the final answer

Solution:

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    if (numRows === 1) return s;
        
    let levels = [];
    for (let i = 0; i < numRows; i++) {
        levels[i] = [];
    }
    let down = true;
    const n = s.length;
    let index = 0;
    for (let i =  0; i < n; i++) {
        if (down) {
            let end = index >= numRows - 1;
            if (end) down = false;
            levels[index].push(s[i]);
            index = end ? index - 1: index + 1;
        } else {
            let top = index <= 0;
            if (top) down = true;
            levels[index].push(s[i]);
            index = top ? index + 1: index - 1;
        }
    }
    let res = "";
    for (let i = 0; i < numRows; i++) {
        res += levels[i].join('');
    }
    return res;
};