如何找到可以从给定句子形成给定缩写词的方法的数量-Java

Question

我正在开发一个单词建立游戏。我陷入了以下情况。我有一个缩写词。另外，我有一个句子，我必须从中确定其形成方式的数量。例如：1缩写：ACM句子：学院关注经理。输出：4。2：缩写：RADAR句子：无线电附加护林员。输出：6基本规则：每个单词中至少应使用一个字符，以构成缩写说明：在第二个示例中，可以使用radio单词rad-ra-r来形成缩写，其后的单词可以实现整个缩写。并且应该维持顺序。到目前为止，我试图做这样的事情public static void checkOccurence(String[] in) {    String word = "";    int k = 0, n;    int total = 0, c = 0;    int extra = 1;    for (int i = 1; i < in.length; i++) {        int v = 0;        n = k;        word = in[i].toUpperCase();        if (k < ab.length()) {            for (int j = 0; j < word.length(); j++) {                if (k < ab.length()) {                    if (word.charAt(j) == ab.charAt(k)) {                        k++;                    }                }            }        }        for (int j = 0; j < word.length(); j++) {            for (int l = 0; l < ab.length(); l++) {                if (word.charAt(j) == ab.charAt(l)) {                    if (j != l && l < k - 1) {                        v += calculateExtra(word, j, l, k);                    } else if (j == l && l < k - 1 && calculateExtra(word, j, l, k) != 1) {                        c++;                    }                }            }        }        v += c;        System.out.println(v);        if (k == n && v > 0) {            v = 0;        }        total += v;    }    if (k == ab.length() && total != 0)        count += total;    if (k == ab.length() && total == 0)        count++;}

Answer 1

我不认为这是完美的，并且我肯定还有很多地方可以改进，但是这里有一个对您的示例都适用的解决方案（可能还有其他一些极端情况），我将其写为如何解决此问题的示例。首先，我们计算所有选项，然后检查哪些节点满足所有条件。一定要注意LowerCase游戏，这很重要！

public class Main {

    public static void main(String[] args) {

    // write your code here

        Node exampleNode = new Node();

        exampleNode.mySentence="academy concern manager".toLowerCase();

        exampleNode.chars="ACM".toLowerCase().toCharArray();

        exampleNode.nextNode();

        System.out.println(getOutput(exampleNode));

        exampleNode = new Node();

        exampleNode.mySentence="Radio addition ranger".toLowerCase();

        exampleNode.chars="RADAR".toLowerCase().toCharArray();

        exampleNode.nextNode();

        System.out.println(getOutput(exampleNode));

    }

    public static int getOutput(Node node){

        int output=0;

        if(node.chars.length==0&& node.mySentence.indexOf(" ")==-1){

            Node nextNode=node;

            String s="";

            while (nextNode!=null){

                 String sub =nextNode.myChar+nextNode.mySentence;

                 s=replaceLast(s.toLowerCase(),"",sub)+s;

                 nextNode = nextNode.father;

            }

            boolean wordWithoutChar = false;

            for (String word:s.split(" ")) {

                boolean noCharInThisWord=true;

                for (char c:word.toCharArray()) {

                    if(c<='Z'&&c>='A'){

                        noCharInThisWord = false;

                    }

                }

                if(noCharInThisWord){

                    wordWithoutChar=noCharInThisWord;

                }

            }

            if(!wordWithoutChar){

                System.out.println(s);

                output++;

            }

        }

        for (Node n:node.nodes) {

            output +=getOutput(n);

        }

        return output;

    }

    public static String replaceLast(String find, String replace, String string) {

        int lastIndex = string.lastIndexOf(find);

        if (lastIndex == -1) {

            return string;

        }

        String beginString = string.substring(0, lastIndex);

        String endString = string.substring(lastIndex + find.length());

        return beginString + replace + endString;

    }

    public static class Node{

        List<Node> nodes = new ArrayList<>();

        Node father =null;

        char myChar=0;

        char[] chars=null;

        String mySentence="";

        public void nextNode() {

            int index=0;

            if(chars.length>0){

                while (index<mySentence.length()){

                    if(mySentence.toCharArray()[index]==chars[0]){

                        Node son = new Node();

                        son.chars = Arrays.copyOfRange(chars, 1, chars.length);

                        son.mySentence=mySentence.substring(index+1);

                        son.father=this;

                        son.myChar= (char) (chars[0]-32);

                        son.nextNode();

                        nodes.add(son);

                    }

                    index++;

                }

            }

            return;

        }

    }

}

输出：

 Academy Concern Manager

 Academy conCern Manager

 acAdemy Concern Manager

 acAdemy conCern Manager

 4

 RADio Addition Ranger

 RADio Addition rangeR

 RAdio aDdition rAngeR

 RAdio adDition rAngeR

 Radio ADdition rAngeR

 Radio AdDition rAngeR

 6