एल्गोरिदम एक शब्द से एक चरित्र को हटाने के लिए जैसे कि कम शब्द अभी भी

Question

में एक शब्द है, यह शब्द परिदृश्य है, एक शब्द को प्रत्येक चरण में एक शब्द से एक वर्ण को हटा दें जैसे कि कम शब्द अभी भी एक शब्द है शब्दकोश। जारी रखें जब तक कोई अक्षर नहीं छोड़ा जाता है।

यहां पकड़ है: आपको सही चरित्र को हटाने की आवश्यकता है, उदाहरण के लिए। एक शब्द में दो संभव वर्ण हो सकते हैं जिन्हें हटाया जा सकता है और दोनों कम शब्द को वैध शब्द मान सकते हैं, लेकिन बाद के चरण में कोई अंत तक कम हो सकता है यानी कोई वर्ण नहीं छोड़ा जा सकता है जबकि दूसरा लटका सकता है।

उदाहरण:

• ग्रह
• संयंत्र
• पैंट
• पैन
• एक
• एक

या

• ग्रह
• विमान
• लेन
• संभव आगे नहीं, मान लीजिए लैन एक शब्द नहीं है। आशा है कि आपको विचार मिल जाएगा।

कृपया मेरा कोड देखें, मैं रिकर्सन का उपयोग कर रहा हूं, लेकिन यह जानना चाहूंगा कि ऐसा करने के लिए बेहतर कुशल समाधान हैं या नहीं।

public class isMashable 
{ 

    static void initiate(String s) 
    { 
    mash("", s); 
    } 

    static void mash(String prefix, String s) 
    { 
    int N = s.length(); 
    String subs = ""; 

    if (!((s.trim()).equals(""))) 
     System.out.println(s); 

    for (int i = 0 ; i < N ; i++) 
    { 
     subs = s.substring(0, i) + s.substring(i+1, N); 
     if (subs.equals("abc")||subs.equals("bc")||subs.equals("c")||subs.equals("a")) // check in dictionary here 
     mash("" + s.charAt(i), subs); 
    } 
    } 

    public static void main(String[] args) 
    { 
    String s = "abc"; 
    initiate(s); 
    } 
} 

Answer 1

एक बीएफएस एल्गोरिदम चलाएं। यदि आपके पास एक से अधिक वर्ण हैं जिन्हें आप हटा सकते हैं, उन्हें अलग-अलग हटाएं और प्राथमिकता कतार में डाल दें, अगर आप पथ को पीछे हटाना चाहते हैं, तो पॉइंटर को माता-पिता को रखें (मूल शब्द जिसमें से आपने इसे हटाकर इस शब्द को बनाया है चरित्र) नोड itslef में शब्द का। और जब आप सभी पात्रों को हटाते हैं, पथ को समाप्त और रिट्रेस करते हैं, या यदि कोई वैध तरीका नहीं है, तो आपके पास खाली प्राथमिकता कतार होगी

Answer 2

ठीक है, यह जावा नहीं है, केवल जावास्क्रिप्ट है, लेकिन शायद आप इसे बदल सकते हैं:

http://jsfiddle.net/BA8PJ/

function subWord(w, p, wrapL, wrapR){ 
    return w.substr(0,p) 
     + (wrapL ? (wrapL + w.substr(p,1) + wrapR):'') 
     + w.substr(p+1); 
} 

// wa = word array:   ['apple','banana'] 
// wo = word object/lookup: {'apple':true,'banana':true} 
function initLookup(){ 
    window.wo = {}; 
    for(var i=0; i < wa.length; i++) wo[ wa[i] ] = true; 
} 



function initialRandomWords(){ 
    // choose some random initial words 
    var level0 = []; 
    for(var i=0; i < 100; i++){ 
    var w = wa[ Math.floor(Math.random()*wa.length) ]; 
    level0.push({ word: w, parentIndex:null, pos:null, leaf:true }); 
    } 
    return level0; 
} 



function generateLevels(levels){ 
    while(true){ 
    var nl = genNextLevel(levels[ levels.length-1 ]); 
    if(! nl) break; 
    levels.push(nl); 
    } 
} 

function genNextLevel(P){ // P: prev/parent level 
    var N = [];    // N: next level 
    var len = 0; 
    for(var pi = 0; pi < P.length; pi ++){ 
    pw = P[ pi ].word; // pw: parent word 
    for(var cp = 0; cp < pw.length; cp++){ // cp: char pos 
     var cw = subWord(pw, cp); // cw: child word 
     if(wo[cw]){ 
     len++; 
     P[ pi ].leaf = false; 
     N.push({ word: cw, parentIndex:pi, pos:cp, leaf:true }); 
     } 
    } 
    } 
    return len ? N : null; 
} 



function getWordTraces(levels){ 
    var rows = []; 
    for(var li = levels.length-1; li >= 0; li--){ 
    var level = levels[ li ]; 
    for(var i = 0; i < level.length; i++){ 
     if(! level[ i ].leaf) continue; 
     var trace = traceWord(li, i); 
     if(trace.length < 2) continue; 
     rows.push(trace); 
    } 
    } 
    return rows; 
} 

function traceWord(li, i){ 
    var r = []; 
    while(true){ 
    var o = levels[ li ][ i ]; 
    r.unshift(o); 
    i = o.parentIndex; 
    if(!i) break; 
    li--; 
    if(li < 0) break; 
    }; 
    return r; 
} 



function compareTraces(aa, bb){ 
    var a = aa[0].word, b = bb[0].word; 
    if(a == b){ 
    if(aa.length < bb.length) return -1; 
    if(aa.length > bb.length) return +1; 
    } 

    var len = Math.min(aa.length, bb.length) 
    for(var i = 0; i < len; i++){ 
    var a = aa[i].word, b = bb[i].word; 
    if(a < b) return +1; 
    if(a > b) return -1; 
    } 

    if(aa.length < bb.length) return -1; 
    if(aa.length > bb.length) return +1; 

    return 0; 
} 


function prettyPrintTraces(rows){ 
    var prevFirstWord = null; 
    for(var ri = rows.length-1; ri >= 0; ri--){ 
    var row = rows[ ri ]; 

    if( prevFirstWord != row[0].word ){ 
     if(prevFirstWord) $('body').append('<div class="sep"/>'); 
     prevFirstWord = row[0].word; 
    } 

    var $row = $('<div class="row"/>'); 
    for(var i = 0; i < row.length; i++){ 

     var w = row[i].word; 
     var c = row[i+1]; 
     if(c) w = subWord(w, c.pos, '<span class="cut">', '</span>'); 

     var $word = $('<div class="word"></div>').html(w).toggleClass('last-word', w.length < 2); 
     $row.append($word); 
    } 
    $('body').append($row); 
    } 
}; 

function main(){ 
    initLookup(); 

    window.levels = [ initialRandomWords() ]; 

    generateLevels(levels); 

    rows = getWordTraces(levels); 

    rows.sort(compareTraces); 

    prettyPrintTraces(rows); 
} 

Answer 3

मैं परियोजनाओं के एक जोड़े में Porter Stemming का इस्तेमाल किया है - निश्चित रूप से है कि इच्छा केवल मदद से आप शब्द के अंत में बंद ट्रिम।

पोर्टर उत्पन्न एल्गोरिथ्म (या 'पोर्टर स्टेमर') अंग्रेजी में शब्द से आम आदमी रूपात्मक और लचीला अंत को हटाने के लिए एक प्रक्रिया है। इसका मुख्य उपयोग शब्द सामान्यीकरण प्रक्रिया के हिस्से के रूप में होता है जो आमतौर पर सूचना पुनर्प्राप्ति प्रणालियों की स्थापना करते समय किया जाता है।

M.F. Porter, 1980, An algorithm for suffix stripping, Program, 14(3) pp 130−137 में एक पुनर्मुद्रण हुआ।

मार्टिन की साइट पर भी Java version available है।

Answer 4

शब्द में दिए गए वर्णों (कोई दोहराव की अनुमति नहीं है) के साथ trie (या suffix tree) बनाएं और शब्दकोश के साथ त्रिभुज के प्रत्येक उप-जांच को जांचें। यह आपकी मदद करनी चाहिए।

संदर्भ यात्रा के लिए

• Suffix tree
• Trie

Answer 5

ये रहा। मैश-विधि को कन्स्ट्रक्टर को पास किए गए शब्दकोश का उपयोग करके किसी भी दिए गए स्ट्रिंग के लिए एक समाधान (शब्दकोष शब्दों की सूची) मिलेगा। यदि कोई समाधान नहीं है (एक अक्षर शब्द को समाप्त करना), विधि शून्य वापस आ जाएगी। यदि आप सभी आंशिक समाधानों में रुचि रखते हैं (एक अक्षर शब्द प्राप्त करने से पहले समाप्त हो रहा है), तो आपको एल्गोरिदम को थोड़ा सा ट्विक करना चाहिए।

शब्दकोश को अपरकेस स्ट्रिंग्स का एक सेट माना जाता है। आप इसके बजाय अपने स्वयं के वर्ग/इंटरफ़ेस का उपयोग कर सकते हैं।

import java.util.ArrayList; 
import java.util.List; 
import java.util.Set; 

public class WordMash { 

    private final Set<String> dictionary; 

    public WordMash(Set<String> dictionary) { 
     if (dictionary == null) throw new IllegalArgumentException("dictionary == null"); 
     this.dictionary = dictionary; 
    } 

    public List<String> mash(String word) { 
     return recursiveMash(new ArrayList<String>(), word.toUpperCase()); 
    } 

    private List<String> recursiveMash(ArrayList<String> wordStack, String proposedWord) { 
     if (!dictionary.contains(proposedWord)) { 
      return null; 
     } 
     wordStack.add(proposedWord); 

     if (proposedWord.length() == 1) { 
      return wordStack; 
     } 

     for (int i = 0; i < proposedWord.length(); i++) { 
      String nextProposedWord = 
       proposedWord.substring(0, i) + proposedWord.substring(i + 1, proposedWord.length());  
      List<String> finalStack = recursiveMash(wordStack, nextProposedWord); 
      if (finalStack != null) return finalStack; 
     } 

     return null; 
    } 

} 

उदाहरण:

Set<String> dictionary = new HashSet<String>(Arrays.asList(
     "A", "AFRICA", "AN", "LANE", "PAN", "PANT", "PLANET", "PLANT" 
)); 
WordMash mash = new WordMash(dictionary); 

System.out.println(mash.mash("planet")); 
System.out.println(mash.mash("pant")); 


System.out.println(mash.mash("foo")); 
System.out.println(mash.mash("lane")); 
System.out.println(mash.mash("africa")); 

Answer 6

यहाँ एक एल्गोरिथ्म गहराई पहले खोज का उपयोग करता है है। एक शब्द को देखते हुए, आप जांचते हैं कि यह मान्य है (शब्दकोश में)। यदि यह मान्य है, तो प्रत्येक इंडेक्स पर स्ट्रिंग से एक वर्ण हटा दें और 'कटा हुआ' शब्द फिर से जांचें। यदि कटा हुआ शब्द किसी भी समय अमान्य है, तो आप गलत रास्ते में हैं और पिछले चरण पर वापस जाएं।

import java.util.HashSet; 
import java.util.Set; 

public class RemoveOneCharacter { 
    static Set<String> dict = new HashSet<String>(); 

    public static boolean remove(String word){ 
     if(word.length() == 1) 
      return true; 

     if(!dict.contains(word)) 
      return false; 

     for(int i=0;i<word.length();i++){ 
      String choppedWord = removeCharAt(word,i); 
      boolean result = remove(choppedWord); 
      if(result) 
       return true; 
     } 
     return false; 
    } 

    public static String removeCharAt(String str, Integer n) { 
     String f = str.substring(0, n); 
     String b = str.substring(n+1, str.length()); 
     return f + b; 
    } 

    public static void main(String args[]){ 
     dict.add("heat"); 
     dict.add("eat"); 
     dict.add("at"); 
     dict.add("a"); 

     dict.add("planets"); 
     dict.add("planet"); 
     dict.add("plant"); 
     dict.add("plane"); 
     dict.add("lane"); 
     dict.add("plants"); 
     dict.add("pant"); 
     dict.add("pants"); 
     dict.add("ant"); 
     dict.add("ants"); 
     dict.add("an"); 


     dict.add("clean"); 
     dict.add("lean"); 
     dict.add("clan"); 
     dict.add("can"); 

     dict.add("why"); 

     String input = "heat"; 
     System.out.println("result(heat) " + remove(input)); 
     input = "planet"; 
     System.out.println("result(planet) " + remove(input)); 
     input = "planets"; 
     System.out.println("result(planets) " + remove(input)); 
     input = "clean"; 
     System.out.println("result(clean) " + remove(input)); 
     input = "why"; 
     System.out.println("result(why) " + remove(input)); 
     input = "name"; 
     System.out.println("result(name) " + remove(input)); 


    } 

}