如何找到可以从给定句子形成给定缩写词的方法的数量-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 {&nbsp; &nbsp; public static void main(String[] args) {&nbsp; &nbsp; // write your code here&nbsp; &nbsp; &nbsp; &nbsp; Node exampleNode = new Node();&nbsp; &nbsp; &nbsp; &nbsp; exampleNode.mySentence="academy concern manager".toLowerCase();&nbsp; &nbsp; &nbsp; &nbsp; exampleNode.chars="ACM".toLowerCase().toCharArray();&nbsp; &nbsp; &nbsp; &nbsp; exampleNode.nextNode();&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(getOutput(exampleNode));&nbsp; &nbsp; &nbsp; &nbsp; exampleNode = new Node();&nbsp; &nbsp; &nbsp; &nbsp; exampleNode.mySentence="Radio addition ranger".toLowerCase();&nbsp; &nbsp; &nbsp; &nbsp; exampleNode.chars="RADAR".toLowerCase().toCharArray();&nbsp; &nbsp; &nbsp; &nbsp; exampleNode.nextNode();&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(getOutput(exampleNode));&nbsp; &nbsp; }&nbsp; &nbsp; public static int getOutput(Node node){&nbsp; &nbsp; &nbsp; &nbsp; int output=0;&nbsp; &nbsp; &nbsp; &nbsp; if(node.chars.length==0&& node.mySentence.indexOf(" ")==-1){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Node nextNode=node;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; String s="";&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while (nextNode!=null){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;String sub =nextNode.myChar+nextNode.mySentence;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;s=replaceLast(s.toLowerCase(),"",sub)+s;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;nextNode = nextNode.father;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; boolean wordWithoutChar = false;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (String word:s.split(" ")) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; boolean noCharInThisWord=true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (char c:word.toCharArray()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(c<='Z'&&c>='A'){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; noCharInThisWord = false;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(noCharInThisWord){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; wordWithoutChar=noCharInThisWord;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(!wordWithoutChar){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println(s);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; output++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; for (Node n:node.nodes) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; output +=getOutput(n);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return output;&nbsp; &nbsp; }&nbsp; &nbsp; public static String replaceLast(String find, String replace, String string) {&nbsp; &nbsp; &nbsp; &nbsp; int lastIndex = string.lastIndexOf(find);&nbsp; &nbsp; &nbsp; &nbsp; if (lastIndex == -1) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return string;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; String beginString = string.substring(0, lastIndex);&nbsp; &nbsp; &nbsp; &nbsp; String endString = string.substring(lastIndex + find.length());&nbsp; &nbsp; &nbsp; &nbsp; return beginString + replace + endString;&nbsp; &nbsp; }&nbsp; &nbsp; public static class Node{&nbsp; &nbsp; &nbsp; &nbsp; List<Node> nodes = new ArrayList<>();&nbsp; &nbsp; &nbsp; &nbsp; Node father =null;&nbsp; &nbsp; &nbsp; &nbsp; char myChar=0;&nbsp; &nbsp; &nbsp; &nbsp; char[] chars=null;&nbsp; &nbsp; &nbsp; &nbsp; String mySentence="";&nbsp; &nbsp; &nbsp; &nbsp; public void nextNode() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int index=0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(chars.length>0){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while (index<mySentence.length()){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(mySentence.toCharArray()[index]==chars[0]){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Node son = new Node();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; son.chars = Arrays.copyOfRange(chars, 1, chars.length);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; son.mySentence=mySentence.substring(index+1);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; son.father=this;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; son.myChar= (char) (chars[0]-32);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; son.nextNode();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; nodes.add(son);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; index++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}输出：&nbsp;Academy Concern Manager&nbsp;Academy conCern Manager&nbsp;acAdemy Concern Manager&nbsp;acAdemy conCern Manager&nbsp;4&nbsp;RADio Addition Ranger&nbsp;RADio Addition rangeR&nbsp;RAdio aDdition rAngeR&nbsp;RAdio adDition rAngeR&nbsp;Radio ADdition rAngeR&nbsp;Radio AdDition rAngeR&nbsp;6