[LeetCode] 30. Substring with Concatenation of All Words

https://leetcode.com/

You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated substring in s is a substring that contains all the strings of any permutation of words concatenated.

 

• For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated substring because it is not the concatenation of any permutation of words.

Return the starting indices of all the concatenated substrings in s. You can return the answer in any order.

Example 1:

nput: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Since words.length == 2 and words[i].length == 3, the concatenated substring has to be of length 6.
The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words.
The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.
The output order does not matter. Returning [9,0] is fine too.

 

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation: Since words.length == 4 and words[i].length == 4, the concatenated substring has to be of length 16. There is no substring of length 16 in s that is equal to the concatenation of any permutation of words.
We return an empty array.

 

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
Explanation: Since words.length == 3 and words[i].length == 3, the concatenated substring has to be of length 9.
The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"] which is a permutation of words. The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"] which is a permutation of words. The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"] which is a permutation of words.

 

Constraints:

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

Code :

function findSubstring(s, words) {
    const result = [];
    const wordLen = words[0].length; // 단어의 길이
    const totalLen = wordLen * words.length; // 모든 단어의 길이 합

    // words 배열의 단어들을 카운트
    const wordCount = {};
    for (const word of words) {
        if (word in wordCount) {
            wordCount[word]++;
        } else {
            wordCount[word] = 1;
        }
    }

    // s 문자열을 순회하며 가능한 모든 부분 문자열을 검사
    for (let i = 0; i <= s.length - totalLen; i++) {
        const substr = s.substr(i, totalLen); // 현재 부분 문자열

        // 현재 부분 문자열을 단어 길이만큼 잘라서 카운트
        const substrCount = {};
        for (let j = 0; j < totalLen; j += wordLen) {
            const word = substr.substr(j, wordLen);
            if (word in substrCount) {
                substrCount[word]++;
            } else {
                substrCount[word] = 1;
            }
        }

        // 현재 부분 문자열과 words의 순열을 비교
        let isPermutation = true;
        for (const word of words) {
            if (!(word in substrCount) || substrCount[word] !== wordCount[word]) {
                isPermutation = false;
                break;
            }
        }

        // 현재 부분 문자열이 words의 순열이면 결과에 추가
        if (isPermutation) {
            result.push(i);
        }
    }

    return result;
}

 

Solutions Code :

// 주어진 문자열 s에서 주어진 단어들이 연결되어 있는지 확인하는 함수
var findSubstring = function(s, words) {
    let res = [];
    let wordLength = words[0].length; // 각 단어의 길이
    let wordCount = words.length; // 단어의 개수
    let len = wordCount * wordLength; // 슬라이딩 윈도우의 길이
    let map = {}
    // 각 단어의 빈도를 해시맵에 저장
    for (let word of words) map[word] = map[word] + 1 || 1; // 단어의 빈도를 해시맵에 저장
    // 슬라이딩 윈도우의 문자열을 생성하고, 각 문자열이 조건에 맞는지 확인하여 결과를 저장
  	for (let i = 0; i < s.length - len + 1; i++) {
            let sub = s.slice(i, i + len); // 슬라이딩 윈도우의 문자열 생성
            if (isConcat(sub, map, wordLength)) res.push(i) // 조건을 만족하는지 확인하여 결과를 저장
        }
    return res;
};
// 주어진 문자열이 주어진 빈도 해시맵에 따라 조건을 만족하는지 확인하는 함수
function isConcat(sub,map,wordLength){
    let seen = {};
    // 주어진 문자열을 단어의 길이를 기준으로 자르고, 각 단어의 빈도를 계산하여 seen 객체에 저장
    for (let i = 0; i < sub.length; i+=wordLength) {
        let word = sub.slice(i,i + wordLength);
        seen[word] = seen[word] + 1 || 1
    }
    // map과 seen 객체를 비교하여 각 단어의 빈도가 일치하는지 확인하여 조건을 만족하는지 판별
    for(let key in map){
        if(map[key] !== seen[key]) return false; //Word freq must match between map and seen
    }
    return true;
}

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode