Bir dizenin iki dizeye bölünüp bölünemeyeceğini nasıl öğrenirim?

Question

Aşağıdaki soruyla görüşme sırasında sorulmuştum. Bu soruya nasıl yaklaşacağımı anlayamadım. Lütfen bana yol göster.

Soru: Bir dizginin iki dizeye ayrılıp bölünemeyeceğini nasıl biliriz - breadbanana ekmek ve muzlara ayrılabilirken, breadbanan olmasa da. Tüm geçerli kelimeleri içeren bir sözlük verilecektir.

Answer 1

Aramayla ilgili daha hızlı arama yapacak sözcüklerin bir trie oluşturun. Ağacınızı giriş dizenizin şu harflerine göre arayın. Ağaçta bulunan bir kelime bulduğunuzda, giriş dizesinde bu kelimeden sonraki konuma yinelemeli olarak başlayabilirsiniz. Giriş dizesinin sonuna gelirseniz, olası bir parçalanma buldunuz. Eğer sıkışmış olsaydınız, geri dönün ve tekrar tekrar başka kelimeler deneyin.

DÜZENLEME: özür dilerim, gerçeği kaçırdı, sadece iki kelime olmalı.

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 

(sen O(1) yılında tray içerisinde bir çocuk düğüme aşağı gidebilir çocukların ASCII endeksleri varsayarsak: Bu durumda , 2 kelime yalancı kod olurdu 2.

için yineleme derinliğini sınırlamak), giriş dizesinin tüm öneklerini O(n+p) adresinde bulabilirsiniz; burada p öneklerin sayısıdır ve girişin uzunluğu n. Üst sınırda bu O(n+m), burada m sözlükteki sözcük sayısıdır. İçermek için denetleme, w'un, m olacağı sözcük uzunluğu olan O(w) alacaktır, bu nedenle, , tüm bulunan sözcüklerin arasındaki ilk aşamada dağıtıldığı için algoritmanın zaman karmaşıklığı O(nm) olur.

Ancak ilk aşamada n sözcükten daha fazlasını bulamadığımız için, karmaşıklık da O(n^2) ile sınırlıdır. Dolayısıyla, arama karmaşıklığı O(n*min(n, m)) olacaktır. Bundan önce O(s) değerini alacağınız trie'yi oluşturmalısınız, burada s sözlükteki sözcüklerin toplamıdır. Bunun üst sınırı, her kelimenin maksimum uzunluğu n olduğundan O(n*m) dur.

Answer 2

basit çözüm:

Bölünmüş ardışık karakterlerin her çifti arasında dize ve her iki alt dizeleri olsun veya olmasın (bölünmüş noktasının solunda ve sağında) bkz sözlükte bulunmaktadır.

Answer 3

Bir yaklaşım olabilir:

Put all elements of dictionary in some set or list

şimdi sözlüğü maçları kelime kaldırmak için contains & substring işlevini kullanabilirsiniz. eğer son dizgede boş ise -> string başkalarına bölünemez. Ayrıca sayım da yapabilirsin.

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(""); 
    } 
} 

Bu kod çekleriniz verilen dize tamamen segmentli edilebilirse. Sözlüğünden bir sözcüğün dizgenin içinde olup olmadığını kontrol eder ve daha sonra onu alt eder. Süreç içinde bölümlemek istiyorsanız, çıkarılmış semententleri kelimenin içinde oldukları sıraya göre sıralamanız gerekir.bir Word için

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; 
    } 
} 

Bu kod kontrolleri ve Dize başka bir kelime ve sadece bu iki kelime varsa aksi false true döndürür:

Sadece iki kelime kolaylaştırır.

Answer 5

Sözlüğünüzü gözden geçirin ve her terimi orijinal terim ile bir alt dizgi olarak karşılaştırın. "Breadbanana". İlk terim ilk alt dize ile eşleşiyorsa, ilk terimini orijinal arama teriminden çıkarın ve diğer sözlük girişlerini orijinal terimin geri kalanıyla karşılaştırın ...

Bunu java'da açıklamaya çalışmama izin verin: Örneğin

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

bu sadece bir fikir, sen o ikisi soran düşünüyorum

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); 
      } 
     } 

    } 

}