Algorithm - LeetCode Problems 3

Problem 392. Is Subsequence

• Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Examples

• Example 1:

• Input: s = "abc", t = "ahbgdc"

• Output: true

• Example 2:

• Input: s = "axc", t = "ahbgdc"

• Output: false

Constraints:

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• s and t consist only of lowercase English letters.

Solution

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function(s, t) {
    let sIndex = 0;
    for (let tIndex = 0; tIndex < t.length; tIndex++) {
        const str = t[tIndex];
        if (s[sIndex] === str) {
            sIndex++;
        }
    }

    return sIndex === s.length;
};

Problem 792. Number of Matching Subsequences

• Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.

• A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

Examples

• Example 1:

  • Input: s = "abcde", words = ["a","bb","acd","ace"]
  • Output: 3
  • Explanation: There are three strings in words that are a subsequence of s: "a", "acd", "ace".

• Example 2:

  • Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
  • Output: 2

Constraints:

• 1 <= s.length <= 5 * 10^4
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• s and words[i] consist of only lowercase English letters.

Solution

• 시간 초과된 풀이 (전체 문자열을 순회)

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number}
 */
var numMatchingSubseq = function(s, words) {
    return words.reduce((sum, word) => {
        let wordIndex = 0;
        for (let sIndex = 0; sIndex < s.length; sIndex++) {
            const str = s[sIndex];
            if (word[wordIndex] === str) {
                wordIndex++;
            }
        }

        if (wordIndex === word.length) {
            sum += 1;
        }

        return sum;
    }, 0);
};

• 다른 사람 풀이를 참고한 풀이 (이전에 찾은 다음 인덱스부터 순회)

var numMatchingSubseq = function(s, words) {
    let subsequenceCount = 0;
    for (const word of words) {
        if (isWordSubsequence(s, word)) {
            subsequenceCount++;
        }
    }
    return subsequenceCount;
};

function isWordSubsequence(s, word) {
    let index = -1;

    for (const str of word) {
        const strIndex = s.indexOf(str, index + 1);
        if (strIndex === -1) {
            return false;
        }
        index = strIndex;
    }
    return true;
}

Problem 763. Partition Labels

• You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

• Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

• Return a list of integers representing the size of these parts.

Examples

• 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.

• Example 2:

  • Input: s = "eccbbbbdec"
  • Output: [10]

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters.

Solution

• 어떤 문자열을 기준으로 파티션을 분할해야 하는지 생각해보기
  • 공통 문자열이 없는 파티션으로 분할해야 하기 때문에, 문자열의 마지막 위치를 기준으로 문자열을 분할한다.
    • 문자열을 하나씩 탐색하면서 해당 문자열의 마지막 위치를 조회한다.
    • 탐색한 문자열의 마지막 위치가 이전 문자열의 마지막 위치보다 뒤에 있으면 갱신한다.
    • 탐색한 문자열의 마지막 위치와 현재의 위치가 일치하면 해당 문자까지 한 파티션으로 분할한다.

var partitionLabels = function(s) {
    const answer = [];
    let lastIndex = -1;
    let startIndex = 0;

    for (let index = 0; index < s.length; index++) {
        lastIndex = Math.max(s.lastIndexOf(s[index]), lastIndex);

        if (index === lastIndex) {
            answer.push(index - startIndex + 1);
            startIndex = index + 1;
        }
    }

    return answer;
};

Problem 56. Merge Intervals

• Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Examples

• Example 1:

  • Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
  • Output: [[1,6],[8,10],[15,18]]
  • Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

• Example 2:

  • Input: intervals = [[1,4],[4,5]]
  • Output: [[1,5]]
  • Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^4

Solution

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
  if (intervals.length < 2) {
    return intervals;
  }
  
  intervals.sort((a, b) => a[0] - b[0]);
  
  for (let i = 1; i < intervals.length; i++) {
    const curr = intervals[i];
    const prev = intervals[i - 1];
    
    if (curr[0] <= prev[1]) {
      intervals[i] = [Math.min(prev[0], curr[0]), Math.max(prev[1], curr[1])];
      intervals.splice(i - 1, 1);
      i--;
    }
  }
  
  return intervals;
}