문자열이 두 개의 문자열로 나눌 수 있는지 알아 보는 방법

Question

다음 인터뷰 질문에서 질문을 받았습니다. 나는이 질문에 접근하는 방법을 알 수 없었다. 나를 안내 해줘.

질문 : 문자열이 두 개의 문자열로 분할 될 수 있는지 여부를 확인하는 방법 - 예를 들어 breadbanana는 빵과 바나나로 세그먼트화할 수 있지만 breadbanan은 그렇지 않습니다. 모든 유효한 단어가 포함 된 사전이 제공됩니다.

Answer 1

사전에있는 단어 중 trie을 빌드하면 검색 속도가 빨라집니다. 입력 문자열의 다음 문자에 따라 트리를 검색하십시오. 나무에있는 단어를 발견하면 입력 문자열에서 해당 단어 다음의 위치에서 반복적으로 시작합니다. 입력 문자열의 끝에 도달하면 가능한 단편화를 발견했습니다. 당신이 붙어 있다면, 돌아와서 재귀 적으로 다른 단어를 시도하십시오.

편집 : 죄송합니다. 사실 두 단어 만 입력해야합니다.

T = trie of words in the dictionary 
for every word in T, which can be found going down the tree by choosing the next letter of the input string each time we move to the child: 
    p <- length(word) 
    if T contains input_string[p:length(intput_string)]: 
     return true 
return false 

(당신이 O(1)의 트라이에 자식 노드로 내려 갈 수있는 아이들의 아스키 인덱스를 가정하면이 경우 는이 개 단어에 대한 의사가 될 것 2.

에 재귀 수준을 제한)을 사용하면 O(n+p)에 입력 문자열의 모든 접두사를 찾을 수 있습니다. 여기서 p은 접두어의 수이고 n은 입력 길이입니다. 이것의 상한은 O(n+m)입니다. 여기에서 m은 사전에있는 단어의 수입니다. 포함하는 것을 확인하는 데 이 걸릴 것입니다. 여기에서 w은 단어의 길이이며, 상한은 m이므로 알고리즘의 시간 복잡도는 O(nm)입니다. O(n)은 발견 된 모든 단어 사이의 첫 번째 단계에 배포되므로 O(nm)입니다.

그러나 우리는 첫 번째 단계에서 n 개 이상의 단어를 찾을 수 없기 때문에 복잡성도 O(n^2)으로 제한됩니다. 그래서 검색 복잡도는 O(n*min(n, m)) 이 될 것입니다. 전에 O(s)이 될 trie를 작성해야합니다. 여기서 s은 사전의 단어 길이 합계입니다. 모든 단어의 최대 길이는 n이므로이 상한은 O(n*m)입니다.

Answer 2

가장 간단한 해결 방법 :

분할 연속 문자의 모든 쌍 사이의 문자열을 모두 문자열 여부 (분리 점의 왼쪽과 오른쪽에있는)를 참조는 사전에 있습니다.

Answer 3

한 가지 방법이 될 수 :

Put all elements of dictionary in some set or list

이제 사전과 일치하는 단어를 제거 contains & substring 기능을 사용할 수 있습니다. 끝 문자열이 null 인 경우 -> 문자열을 세그먼트화할 수 없습니다. 카운트도 처리 할 수 ​​있습니다.

Answer 4

public boolean canBeSegmented(String s) { 
    for (String word : dictionary.getWords()) { 
     if (s.contains(word) { 
      String sub = s.subString(0, s.indexOf(word)); 
      s = sub + s.subString(s.indexOf(word)+word.length(), s.length()-1); 
     } 

     return s.equals(""); 
    } 
} 

이 코드는 지정된 문자열을 완전히 세그먼트화할 수 있는지 확인합니다. 사전에서 단어가 문자열 안에 있는지 확인한 다음 문자열을 중첩시킵니다. 당신이 과정에서 그것을 분열하기를 원한다면 당신은 단어 안에있는 순서대로 빼낸 sementents를 주문해야합니다.한 단어에 대한

public boolean canBeSegmented(String s) { 
    boolean wordDetected = false; 

    for (String word : dictionary.getWords()) { 
     if (s.contains(word) { 
      String sub = s.subString(0, s.indexOf(word)); 
      s = sub + s.subString(s.indexOf(word)+word.length(), s.length()-1); 

      if(!wordDetected) 
       wordDetected = true; 
      else 
       return s.equals(""); 
     } 

     return false; 
    } 
} 

이 코드 검사 및 String의 다른 단어 바로이 두 단어가있는 경우는 그렇지 않은 경우는 false true를 돌려 :

그냥 두 단어는 쉽게한다.

Answer 5

당신은 사전을 살펴보고 모든 용어를 하위 문자열로 원래 용어와 비교합니다. "breadbanana". 첫 번째 용어가 첫 번째 하위 문자열과 일치하는 경우 첫 번째 용어를 원래 검색어에서 잘라내어 다음 단어 항목을 원래 용어의 나머지 단어와 비교하십시오.

Java에서 설명해 드리겠습니다. 예

String dictTerm = "bread"; 
    String original = "breadbanana"; 

    // first part matches 
    if (dictTerm.equals(original.substring(0, dictTerm.length()))) { 
     // first part matches, get the rest 
     String lastPart = original.substring(dictTerm.length()); 

     String nextDictTerm = "banana"; 

     if (nextDictTerm.equals(lastPart)) { 
      System.out.println("String " + original + 
       " contains the dictionary terms " + 
       dictTerm + " and " + lastPart); 
     } 
    } 

Answer 6

이 단순한 아이디어는, 당신은 당신은 내가이 양을 요구 생각

package farzi; 

import java.util.ArrayList; 

public class StringPossibility { 
    public static void main(String[] args) { 
     String str = "breadbanana"; 
     ArrayList<String> dict = new ArrayList<String>(); 
     dict.add("bread"); 
     dict.add("banana"); 
     for(int i=0;i<str.length();i++) 
     { 
      String word1 = str.substring(0,i); 
      String word2 = str.substring(i,str.length()); 
      System.out.println(word1+"===>>>"+word2); 
      if(dict.contains(word1)) 
      { 
       System.out.println("word 1 found : "+word1+" at index "+i); 
      } 
      if(dict.contains(word2)) 
      { 
       System.out.println("word 2 found : "+ word2+" at index "+i); 
      } 
     } 

    } 

}