में विभाजित किया जा सकता है, मुझे प्रश्न के बाद साक्षात्कार में पूछा गया था। मैं इस प्रश्न से संपर्क करने का तरीका नहीं समझ पाया। कृपया मेरा मार्ग दर्शन कीजिए।कैसे पता चलेगा कि स्ट्रिंग को दो स्ट्रिंग्स
प्रश्न: कैसे पता चले कि एक स्ट्रिंग को दो तारों में विभाजित किया जा सकता है - जैसे कि ब्रेडबानाना रोटी और केले में विभाजित है, जबकि ब्रेडबानन नहीं है। आपको एक शब्दकोश दिया जाएगा जिसमें सभी वैध शब्द होंगे।
शब्दकोश में आपके द्वारा दिए गए शब्दों में से trie बनाएं, जो तेजी से खोज करेगा। अपनी इनपुट स्ट्रिंग के निम्न अक्षरों के अनुसार पेड़ को खोजें। जब आपको एक शब्द मिल गया है, जो पेड़ में है, इनपुट स्ट्रिंग में उस शब्द के बाद स्थिति से रिकर्सिव से शुरू होता है। यदि आप इनपुट स्ट्रिंग के अंत तक पहुंच जाते हैं, तो आपको एक संभावित विखंडन मिल गया है। अगर आप अटक गए हैं, तो वापस आएं और दोबारा शब्दों का प्रयास करें।
संपादित करें: क्षमा करें, इस तथ्य को याद किया, कि केवल दो शब्द होना चाहिए। इस मामले में, करने के लिए 2.
प्रत्यावर्तन गहराई की सीमा 2 शब्दों के लिए स्यूडोकोड होगा:
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) में trie में एक बच्चे नोड के लिए नीचे जा सकता है बच्चों की ascii अनुक्रमित), आप इनपुट स्ट्रिंग के सभी उपसर्ग O(n+p) में पा सकते हैं, जहां p उपसर्गों की संख्या है, और इनपुट की लंबाई n है। इस पर ऊपरी सीमा O(n+m) है, जहां m शब्दकोश में शब्दों की संख्या है। युक्त के लिए जांच O(w) ले जाएगी जहां w शब्द की लंबाई है, जिसके लिए ऊपरी सीमा m होगी, इसलिए एल्गोरिदम की समय जटिलता O(nm) है, क्योंकि O(n) सभी पाए गए शब्दों के बीच पहले चरण में वितरित की जाती है।
लेकिन क्योंकि हम पहले चरण में n शब्दों से अधिक नहीं पा रहे हैं, जटिलता भी O(n^2) तक सीमित है। तो खोज जटिलता O(n*min(n, m)) इससे पहले कि आपको ट्राई बनाने की आवश्यकता है जो O(s) ले जाएगा, जहां s शब्दकोश में शब्दों की लंबाई का योग है। इस पर ऊपरी सीमा O(n*m) है, क्योंकि प्रत्येक शब्द की अधिकतम लंबाई n है।
दिलचस्प। मेरा विचार था कि पहले शब्द का पता लगाने के लिए एक त्रिभुज का उपयोग करना था, और यदि पाया गया तो शब्दकोश में दूसरे शब्द के लिए त्वरित, स्थिर समय खोज करें। मुझे लगता है कि व्यापक मार्जिन द्वारा प्रस्तावित अन्य प्रस्तावित समाधानों को धड़कता है। किसी भी मामले में, आपको +1। – Perception
@ धारणा: यह अभी भी 'ओ (एन)' खोज है, नहीं? – NPE
@ माइकलट्रीबस: यदि आपके उत्तर में आपके प्रस्तावित एल्गोरिदम की समय जटिलता शामिल है तो यह सहायक होगा। – NPE
सरल समाधान:
स्प्लिट लगातार पात्रों के हर जोड़ी के बीच स्ट्रिंग और चाहे या नहीं दोनों सबस्ट्रिंग (विभाजन बिंदु के बाईं ओर और उसके दाईं ओर स्थित) को देखने के शब्दकोश में हैं।
और डाउनवॉटिंग का कारण क्या था? –
एक दृष्टिकोण हो सकता है:
Put all elements of dictionary in some set or list अब आप जो शब्द शब्दकोश से मेल खाता है दूर करने के लिए contains & substring फ़ंक्शन का उपयोग कर सकते हैं। यदि अंत में स्ट्रिंग शून्य है -> स्ट्रिंग को विभाजित किया जा सकता है अन्यथा नहीं। आप गिनती का भी ख्याल रख सकते हैं।
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("");
}
}
यह कोड जांचता है कि क्या आपके दिए गए स्ट्रिंग को पूरी तरह से विभाजित किया जा सकता है। यह जांचता है कि शब्दकोश का एक शब्द आपकी स्ट्रिंग के अंदर है और फिर इसे घटा देता है। यदि आप इसे प्रक्रिया में विभाजित करना चाहते हैं तो आपको शब्द के अंदर दिए गए क्रम में घटित सिमेंटेंट को ऑर्डर करना होगा।एक पद के लिए
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;
}
}
इस कोड को चेक और अगर वहाँ सिर्फ इन दो शब्दों स्ट्रिंग में एक और शब्द और है यह सच अन्यथा गलत रिटर्न:
सिर्फ दो शब्द ढूंढना आसान बनाता है।
आप अपने शब्दकोश के माध्यम से जाते हैं और मूल शब्द के साथ एक सबस्ट्रिंग के रूप में हर शब्द की तुलना करें। "Breadbanana"। यदि पहला शब्द पहले सबस्ट्रिंग के साथ मेल खाता है, तो मूल शब्द अवधि से पहले शब्द काट लें और शेष मूल शब्द के साथ अगली शब्दकोश प्रविष्टियों की तुलना करें ...
मुझे जावा में यह बताने की कोशिश करें: जैसे
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);
}
}
इस एक मात्र विचार है, तो आप इसे बेहतर लागू कर सकते हैं अगर आप चाहते हैं
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);
}
}
}
}
मुझे लगता है कि वह दोनों के लिए पूछ रहा है। – Blizzer