从单词列表中查找使用最多字母的单词的算法 [英] Algorithm to find words that uses most letters that I have from the word list

问题描述

我正在开发一款游戏，我需要一种算法来查找使用最多字母的单词.

I am developing a game I need an algorithm to find words that use most letters.

L,A,B,K,C,O,L,N,A,E 可以用这些字母构成的单词

L,A,B,K,C,O,L,N,A,E words that can be constructed with these letters

ABACK ABLE ACNE ALACK ALACK ALAN ALBA ALEC ALOE ALONE ANAL ANKLE BAAL BACK BACON BAKE BALK BALL BALLON BANAL BANCO BANE BANK BEACON BECK BEAN BECK BECKON BELL细胞 CELLO CLAN CLANK CLEAN CLOAK CLONE COAL COOK COLE CONE EBON ELAN KALE KANA KENO KNELL KNOLL 标签花边 LACK LANCE LANCE LANK LEAK LEAL LEAN LOAN LOBE LOCA LOCAL LOCALE LOCK ONE LONE

ABACK ABLE ACNE ALACK ALAN ALBA ALEC ALOE ALONE ANAL ANKLE BAAL BACK BACON BAKE BALANCE BALE BALK BALL BALLON BANAL BANCO BANE BANK BEACON BEAK BEAN BECK BECKON BELL BLACK BLACKEN BLANK BLEAK BLOC BLOCK BLOKE BOCK BOLE BONE CABAL CABLE CAKE CALL CANAL CANE CANOE CELL CELLO CLAN CLANK CLEAN CLOAK CLONE COAL COKE COLA COLE CONE EBON ELAN KALE KANA KANE KENO KNELL KNOB KNOLL LABEL LACE LACK LAKE LANCE LANE LANK LEAK LEAL LEAN LOAN LOBE LOCA LOCAL LOCALE LOCK LONE NALA NECK NOBLE NOEL OAKEN OCEAN OLLA ONCE

我需要一种算法来查找使用大部分字母的单词组合.字母可以使用一次.我可以用蛮力算法找到它我可以取出一个单词并尝试用我留下的字母找到另一个单词.但我想构建更优雅的算法.

I need an algorithm that finds words combination that uses most of the letters. letters can be used once. I can find it with brute force algorithm I can take out one word and try to find another word with the letters I have left. But I want to build more elegant algorithm.

public class FindBetsWords {

    private static String wordsStr = "ABACK,ABAFT,ABATE,ABBA,ABBE,ABBOT,ABET,ABLAZE,ABLE,ABOUT,ACME,ACNE,ACTA,ACTUAL,ACUMEN,ACUTE,AFFABLE,AFFECT,AFLAME,AFLOAT,ALACK,ALAMO,ALAN,ALBA,ALBUM,ALBUMEN,ALEC,ALFA,ALLOT,ALMA,ALOE,ALOFT,ALONE,ALTO,ALUM,AMAZE,AMAZON,AMBLE,AMEN,AMOUNT,AMULET,ANAL,ANKLE,ANTE,ATOLL,ATOM,ATONE,AUNT,AUTO,BAAL,BABA,BABE,BABEL,BABU,BACK,BACON,BAFFLE,BAKE,BALANCE,BALBOA,BALE,BALEFUL,BALK,BALL,BALLET,BALLON,BALLOT,BALM,BANAL,BANCO,BANE,BANEFUL,BANK,BANTAM,BATE,BATEAU,BATMAN,BATON,BAUBLE,BEACON,BEAK,BEAM,BEAN,BEAT,BEAU,BECK,BECKON,BEFALL,BELL,BELT,BEMOAN,BENT,BETA,BLAB,BLACK,BLACKEN,BLAME,BLANK,BLANKET,BLAZE,BLAZON,BLEAK,BLEAT,BLENT,BLOC,BLOCK,BLOKE,BLOT,BLUE,BLUFF,BLUME,BLUNT,BOAT,BOATMAN,BOATMEN,BOCK,BOLE,BOLT,BOMB,BONE,BOULE,BOUNCE,BOUT,BUCK,BUCKET,BUCKLE,BUFF,BUFFALO,BUFFET,BULB,BULK,BULL,BULLET,BULLOCK,BUMBLE,BUNK,BUNT,BUTE,CABAL,CABLE,CABMAN,CABMEN,CAFE,CAKE,CALF,CALL,CALM,CALOMEL,CAME,CAMEL,CAMEO,CANAL,CANE,CANOE,CANT,CANTO,CATE,CELL,CELLO,CELT,CENT,CENTO,CENTUM,CLAM,CLAN,CLANK,CLEAN,CLEF,CLEFT,CLOAK,CLOMB,CLONE,CLOT,CLOUT,CLUB,CLUE,COAL,COAT,COBALT,COBB,COFFLE,COKE,COLA,COLE,COLLET,COLT,COLUMN,COMA,COMB,COMBAT,COMBE,COME,COMET,COMTE,CONE,CONFUTE,CONTE,COTE,COUNT,COZEN,CUBE,CUFF,CULL,CULT,CUTE,EBON,ECLAT,ELAN,ENACT,ETNA,FABLE,FACE,FACT,FACTUAL,FAKE,FALCON,FALL,FALLEN,FAME,FANE,FATAL,FATE,FATEFUL,FAUCET,FAULT,FAUN,FAUNA,FEAT,FELL,FELLA,FELON,FELT,FETAL,FLACK,FLACON,FLAKE,FLAM,FLAME,FLANK,FLAT,FLAUNT,FLEA,FLECK,FLOAT,FLOCK,FLOE,FLOUNCE,FLOUT,FLUE,FLUENT,FLUKE,FLUME,FLUTE,FOAL,FOAM,FOCAL,FOEMAN,FOLK,FOMENT,FONT,FOUL,FOUNT,FUEL,FULL,FUMBLE,FUME,FUNK,KALE,KANA,KANE,KATA,KENO,KENT,KNACK,KNELL,KNELT,KNOB,KNOCK,KNOLL,KNOT,KNOUT,KNUCKLE,LABEL,LACE,LACK,LACUNA,LAKE,LAMA,LAMB,LAMBENT,LAME,LAMENT,LANCE,LANCET,LANE,LANK,LATE,LATEN,LEAF,LEAK,LEAL,LEAN,LEANT,LEFT,LEMAN,LEMON,LENT,LENTO,LLAMA,LOAF,LOAM,LOAN,LOBE,LOCA,LOCAL,LOCALE,LOCATE,LOCK,LOCKET,LOCUM,LOFT,LONE,LOUT,LUCE,LUCENT,LUCK,LUMEN,LUNA,LUNE,LUTE,MACE,MACK,MACON,MAKE,MALE,MALL,MALLET,MALT,MANA,MANE,MANFUL,MANO,MANTEAU,MANTEL,MANTLE,MANTUA,MANUAL,MATE,MAUL,MAUN,MAZE,MEAL,MEAN,MEANT,MEAT,MELL,MELON,MELT,MELTON,MENO,MENTAL,MENU,META,METAL,MOAN,MOAT,MOCK,MOLE,MOLL,MOLTEN,MONK,MONTE,MOTE,MOTEL,MOUE,MOULT,MOUNT,MUCK,MUCKLE,MUFF,MUFFLE,MULE,MULL,MULLET,MUTABLE,MUTE,NABOB,NALA,NAME,NATAL,NEAT,NEBULA,NECK,NOBLE,NOEL,NOME,NOTA,NOTABLE,NOTE,NUKE,NULL,NUMB,OAKEN,OAKUM,OATEN,OATMEAL,OCEAN,OFFAL,OFTEN,OLLA,OMEN,ONCE,OUNCE,OUTBACK,TABLE,TABLEAU,TABU,TACK,TACKLE,TACO,TAKE,TAKEN,TALA,TALE,TALK,TALL,TALON,TAME,TANK,TEAK,TEAL,TEAM,TELA,TELAMON,TELCO,TELL,TOKEN,TOLE,TOLL,TOMB,TOME,TONE,TUBAL,TUBE,TUCK,TUFA,TULE,TULLE,TUMBLE,TUNA,TUNE,UNABLE,UNCLE,UNCO,UNFELT,UNLOCK,UNMAKE,UNTO,ZEAL,ZEALOT,ZETA,ZONE";

    public static void main(String[] args) {
        String availableLetters = "LABKCOLNAEMFKUTFZB";
        char[] availableLettersCharArr = availableLetters.toCharArray();

        String[] words = wordsStr.split(",");
    }
}

推荐答案

它被称为加权集合打包问题，权重是字符串的长度，正如 David 在 这篇文章.这是一个NP完全问题.在这篇论文中可以找到近似解和最优解.但我没有时间读它.

It is called a weighted set packing problem, with the weight being the length of string, as pointed out by David in this post. It is an NP-complete problem. Both approximation and optimal solutions could be found in this paper. But I haven't had time to read it.

这篇关于从单词列表中查找使用最多字母的单词的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！