해결 방안: 단어의 간단한 인코딩(2판)

22781 단어 algorithmsjavascriptpythonjava
일련의 Letcode 솔루션 설명()의 일부입니다.만약 당신이 이 해결 방안을 좋아하거나 유용하다고 생각한다면 이 댓글과/또는 투표 my solution post on Leetcode's forums을 좋아하세요.
주의: 이것은 내가 이 문제에 대한 두 번째 해결 방안이다.이 문제가 열거한 제한 조건은 성능이 높은 해결 방안이지만 이 문제의 본질은 확실히 Trie 해결 방안이 필요하기 때문에 나도 여기에 Trie 방법의 해체를 포함한다.

질문 #820 (중): 단어의 간단한 인코딩


설명:


(점프: Solution Idea | | 코드: JavaScript | Python | Java | C++ |

A valid encoding of an array of words is any reference string s and array of indices indices such that:

  • words.length == indices.length
  • The reference string s ends with the '#' character.
  • For each index indices[i], the substring of s starting from indices[i] and up to (but not including) the next '#' character is equal to words[i].

Given an array of words, return the length of the shortest reference string s possible of any valid encoding of words.


예를 들면 다음과 같습니다.


Example 1:
Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"
Example 2:
Input: words = ["t"]
Output: 2
Explanation: A valid encoding would be s = "t#" and indices = [0].

제한 사항:


  • 1 <= words.length <= 2000
  • 1 <= words[i].length <= 7
  • words[i] consists of only lowercase letters.

생각:


(점프: Problem Description | | 코드: JavaScript | Python | Java | C++ |
따라서 입력한 간단한 인코딩은 각 단어의 끝에 '#' 표시를 추가한 다음 문자열로 연결하는 것이다.설명에 따르면 두 개 이상의 단어를 하나의 인코딩 단어로 조합할 수 있다면 이런 인코딩을 줄일 수 있다.이를 위해 작은 단어는 큰 단어의 하위 문자열일 뿐만 아니라 맨 오른쪽의 하위 문자열이나 접미사여야 한다.
여기서 간단한 해결 방안은 단어 하나하나를 다른 단어와 비교하고 비교적 큰 단어가 접미사로 적은지 확인하는 것이다. 그러나 최대 2000개의 단어가 있다면 400만 개에 가까운 조합이 가능하다는 뜻이다.
그러나 만약 우리가 일치하는 접두사를 검사할 것을 요구한다면,trie 솔루션도 고려할 수 있습니다.trie는 트리 데이터 구조로 접두사 (또는 이 예에서 접두사) 데이터의 지점을 정의합니다.이렇게 하면 같은 접두사를 공유하는 항목이 한데 묶여 식별하기 쉽다.
trie를 구축할 때 데이터의 입도 세그먼트를 옮겨다니며, trie의 기존 지점이 존재할 때 옮겨다니며, 존재하지 않을 때 만들어집니다. 이 문제에 대해 항목은 단어이기 때문에 입도 세그먼트는 문자입니다.우리는 접두사가 아니라 접두사를 처리하기 때문에 문자를 상반된 순서로 훑어볼 것이다.

우리는 Trie를 완전히 구축한 다음에 Trie를 반복해서 우리의 답안(ans)을 계산할 수 있지만 Trie를 구축할 때 ans의 최신 상태를 유지하여 효율을 높일 수 있다.
우리가 Trie를 건설하는 과정에서 우리는 반드시 세 가지를 주의해야 한다.
  • 만약 한 단어를 처리할 때 어떤 새로운 지점이 형성되었다면 이 단어는 반드시 새것이어야 한다. 우리는 그것의 길이(1을 더하면 끝을 나타내는'#')를 ans에 추가해야 한다.
  • 만약 한 단어의 끝에 새로운 지점이 형성되지 않았다면, 그것은 반드시 초기 단어의 접미사여야 하기 때문에, 우리는 그 길이를 우리의 답안에 추가해서는 안 된다.
  • 만약에 한 단어를 처리할 때 노드에 첫 번째 새로운 지점의 다른 지점이 형성되지 않는다면 비교적 빠른 단어는 반드시 현재 단어의 접미사이어야 하기 때문에 우리는 ans에서 이미 추가된 수량을 줄여야 한다.
    특히 세 번째 검사는 들어가기 전에 W에 대한 정렬을 피할 수 있도록 할 것이다.단어가 새 영역으로 확장될 때마다 (새 문자마다 이런 상황이 발생할 수 있음) 세 번째 검사를 촉발하는 것을 방지하기 위해서, 우리는 볼 로고 (newWord) 를 사용하여 첫 번째 실례만 표시할 수 있습니다.

    구현:


    Javascript와 Python은 Trie를 실현할 때 더욱 간단합니다.그들은 더욱 간단한 지도 구조를 사용하여 잘 사용할 수 있다.
    그러나 자바와 C++에 대해 우리는trie에서 더 많은 비용이 드는 데이터 구조를 사용하지 않고 클래스 구조를 사용하기를 희망한다. 우리는 각 노드를 26개의 요소의 그룹으로 간소화함으로써 효율을 높일 수 있고, 색인마다 한 문자에 대응할 수 있다.
    맵 유형의 대상에서 질서 있는 그룹으로 전환할 때, 우리가 직면한 또 다른 문제는, 그룹이 완전히 비어 있는지 아닌지를 판단하는 간단한 방법이 없다는 것이다.이 문제를 해결하기 위해서, 우리는 우리의 세 노드 클래스에 등공블로고를 추가할 수 있다.

    Javascript 코드:


    (점프: Problem Description | | Solution Idea)
    var minimumLengthEncoding = function(W) {
    let len = W.length, trie = new Map(), ans = 1
    for (let word of W) {
        let curr = trie, newWord = false
        for (let j = word.length - 1; ~j; j--) {
            let char = word.charAt(j)
            if (!curr.size && !newWord)
                ans -= word.length - j
            if (!curr.has(char))
                newWord = true, curr.set(char, new Map())
            curr = curr.get(char)
        }
        if (newWord) ans += word.length + 1
    }
    return ans
};

    파이썬 코드:


    (점프: Problem Description | | Solution Idea)
    class Solution:
    def minimumLengthEncoding(self, W: List[str]) -> int:
        trie, ans = defaultdict(), 1
        for word in W:
            curr, newWord = trie, False
            for i in range(len(word)-1,-1,-1):
                char = word[i]
                if not curr and not newWord: ans -= len(word) - i
                if char not in curr:
                    newWord = True
                    curr[char] = defaultdict()
                curr = curr[char]
            if newWord: ans += len(word) + 1
        return ans

    Java 코드:


    (점프: Problem Description | | Solution Idea)
    class TrieNode {
    TrieNode[] branch = new TrieNode[26];
    Boolean isEmpty = true;
}

class Solution {
    public int minimumLengthEncoding(String[] W) {
        TrieNode trie = new TrieNode();
        trie.branch = new TrieNode[26];
        int ans = 1;
        for (String word : W) {
            TrieNode curr = trie;
            Boolean newWord = false;
            for (int i = word.length() - 1; i >= 0; i--) {
                int c = word.charAt(i) - 'a';
                if (curr.isEmpty && !newWord) ans -= word.length() - i;
                if (curr.branch[c] == null) {
                    curr.branch[c] = new TrieNode();
                    newWord = true;
                    curr.isEmpty = false;
                }
                curr = curr.branch[c];
            }
            if (newWord) ans += word.length() + 1;
        }
        return ans;
    }
}

    C++ 코드:


    (점프: Problem Description | | Solution Idea)
    struct TrieNode {
    TrieNode *branch[26];
    bool isEmpty = true;
};

class Solution {
public:
    int minimumLengthEncoding(vector<string>& W) {
        TrieNode *trie = new TrieNode();
        int ans = 1;
        for (string word : W) {
            TrieNode *curr = trie;
            bool newWord = false;
            for (int i = word.size() - 1; i >= 0; i--) {
                int c = word[i] - 97;
                if (curr->isEmpty && !newWord) ans -= word.size() - i;
                if (!curr->branch[c]) {
                    newWord = true;
                    curr->branch[c] = new TrieNode();
                    curr->isEmpty = false;
                }
                curr = curr->branch[c];
            }
            if (newWord) ans += word.size() + 1;
        }
        return ans;
    }
};
    • TabBarController의 Swift 버전 사용
    AWS SDK for PHP를 사용하여 SMS로 메시지 보내기

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage