Algorithm - LeetCode Problems 11

Problem 844. Backspace String Compare

• Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

• Note that after backspacing an empty text, the text will continue empty.

Examples

• Example 1:

  • Input: s = "ab#c", t = "ad#c"
  • Output: true
  • Explanation: Both s and t become "ac".

• Example 2:

  • Input: s = "ab##", t = "c#d#"
  • Output: true
  • Explanation: Both s and t become "".

• Example 3:

  • Input: s = "a#c", t = "b"
  • Output: false
  • Explanation: s becomes "c" while t becomes "b".

Constraints

• 1 <= s.length, t.length <= 200
• s and t only contain lowercase letters and '#' characters.

Solution

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function(s, t) {
    return excuteBackspace(s) === excuteBackspace(t);
};

var excuteBackspace = function(str) {
    const stack = [];

    for (let i = 0; i < str.length; i++) {
        if (str[i] === '#') {
            stack.pop();
        } else {
            stack.push(str[i]);
        }
    }

    return stack.join('');
}

Problem 784. Letter Case Permutation

• Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.

• Return a list of all possible strings we could create. Return the output in any order.

Examples

• Example 1:

  • Input: s = "a1b2"
  • Output: ["a1b2","a1B2","A1b2","A1B2"]

• Example 2:

  • Input: s = "3z4"
  • Output: ["3z4","3Z4"]

Constraints:

• 1 <= s.length <= 12
• s consists of lowercase English letters, uppercase English letters, and digits.

Solution

/**
 * @param {string} s
 * @return {string[]}
 */
var letterCasePermutation = function(s) {
    const alphabetRegExp = /[a-zA-Z]/;
    const result = [];

    const getPermutation = function (index, arr) {
        if (arr.length === s.length) {
            result.push(arr.join(''));
            return;
        }

        const letter = s[index];
        if (alphabetRegExp.test(letter)) {
            getPermutation(index + 1, [...arr, letter.toLowerCase()]);
            getPermutation(index + 1, [...arr, letter.toUpperCase()]);
        } else {
            getPermutation(index + 1, [...arr, letter]);
        }
    }

    getPermutation(0, []);
    return result;
}

Problem 557. Reverse Words in a String III

• Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Examples

• Example 1:
  • Input: s = "Let's take LeetCode contest"
  • Output: "s'teL ekat edoCteeL tsetnoc"
• Example 2:
  • Input: s = "God Ding"
  • Output: "doG gniD"

Constraints

• 1 <= s.length <= 5 * 10^4
• s contains printable ASCII characters.
• s does not contain any leading or trailing spaces.
• There is at least one word in s.
• All the words in s are separated by a single space.

Solution

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    return s.split(' ').map((str) => {
        let reversedStr = '';
        for (let i = str.length - 1; i >=0; i--) {
            reversedStr = reversedStr + str[i];
        }
        return reversedStr;
    }).join(' ');
};