단어 나누기

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 ByteDance 이베이 Facebook 구글 Microsoft 신탁 Qualtrics 동네 짱 VM웨어 Yahoo
알고리즘 코딩 동적 프로그래밍 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 70

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

단어 나누기 완전히 새로운 개념을 아름답게 보여주는 문제입니다. 우리는 모두 복합어에 대해 들어 보았습니다. 둘 이상의 단어로 구성된 단어 단어. 오늘 우리는 단어 목록을 가지고 있고 우리가해야 할 일은 사전의 모든 단어가 우리의 합성어를 만들기에 적합한 지 확인하는 것입니다. 더 이상 시간을 낭비하지 않고 문제를 해결하기 위해 테스트 케이스로 이동하겠습니다.

입력 : String = LeetCode; 사전 : [ "Leet", "Code"]

출력 : 참

우리도 거짓이되어야하는 테스트 케이스를 살펴 보자

입력 : 문자열 = Applepinkraft; 사전 : [ "Apple", "Pink", "Kraft"]

출력 : false

설명

이 단어 분리 문제를 해결하기위한 첫 번째 테스트 사례를 살펴 보겠습니다.

  • 부울을 만듭니다. 정렬 모든 캐릭터에 대해. 확인하자.
  • 기본값을 false로 설정합니다.
  • check [i] = true if substring (0, i)은 사전에있는 단어로 조합 할 수 있습니다.
  • check [0] = true as substring (0,0)이 조건을 충족 함
  • 각각에 대해
    • 가능한 모든 하위 문자열을 반복합니다.
    • 하위 문자열을 적격하게 만드는 것은 무엇입니까?
      • 마지막 세그먼트의 끝에서 시작해야합니다. 즉, check [j] = true
      • substring (j, i)는 사전의 일부 여야합니다.
    • 모든 적격 하위 문자열에 대해 check [i] true로 표시
  • check [string.length ()]가 참이면 우리는 자격이되는

초기 부울 배열은 다음과 같이 그릴 수 있습니다.

예제 LeetCode에 대한 단어 나누기 설명
예제 LeetCode에 대한 단어 나누기 설명

I의 값이 2와 3 일 때 배열은 동일하게 유지됩니다.

i = 4로 0부터 스캔을 시작하고 짜잔!. 첫 번째 단어를 찾았습니다.

check [4]를 참으로 표시하고 검색을 계속합니다.

계속 진행하면서 단어 나누기 확인
계속 진행하면서 단어 나누기 확인

0과 4로 시작하는 단어는 모두 확인하는 동안 고려됩니다.

우리가 CODE를 찾는 것처럼. check [8]을 참으로 바꾸고 답으로 참을 반환합니다.

다음은 위의 설명으로 이동하기 쉬운 코드입니다.

실시

단어 나누기를위한 자바 코드

class Solution 
{
    public boolean wordBreak(String s, List<String> wordDict) 
    {
        boolean check[]=new boolean[s.length()+1];
        check[0]=true;
        for(int i=1;i<=s.length();i++)
        {
            for(int j=0;j<i;j++)
            {
                //check[j] helps us to figure out new words without overlaps
                if(check[j] && wordDict.contains(s.substring(j,i)))
                {check[i]=true;break;}
            }
        }
        return check[s.length()];
    }
}

단어 나누기를위한 C ++ 코드

class Solution 
{
public:
    bool wordBreak(string s, vector<string>& vec) 
    {
        vector<bool> check(s.size()+1,false);
        check[0]=true;
        int start=0;
        std::vector<string>::iterator it; 
        for(int i=1;i<=s.length();i++)
        {
            for(int j=start;j<i;j++)
            {
                if(check[j]==true)
                {
                    string word=s.substr(j,i);
                    it = std::find (vec.begin(), vec.end(), word); 
                    if (it != vec.end()) 
                    {check[i]=true;break;}
                }
            }
        }
        return check[s.length()];   
    }
};
String: LeetCode  
Dictionary: ["Leet","Code"]
true

복잡성 분석

시간 복잡도 : O (n ^ 2) 여기서 n은 배열의 길이입니다. 여기서는 두 번째 루프가 i 번 실행되고 첫 번째 루프가 n 번 실행되는 중첩 for 루프를 사용합니다.

공간 복잡성 : O (n) 왜냐하면 정보를 참 또는 거짓으로 저장하기 위해 크기 n의 벡터를 생성하기 때문입니다.

많이있다 문자열 문제 더 많은 연습을 위해 확인할 수 있습니다.

참조

균열 시스템 설계 인터뷰
Translate »