LEET代码2744.查找最大数量的字符串对数
#java #leetcode #字符串 #interviewquestions

这是一个简单的problem,描述为:

您给出了一个由不同字符串组成的0个索引数组单词。

字符串单词[i]可以与字符串单词[J]配对:

字符串单词[i]等于词语的字符串[J]。

0 <= i

返回可以从数组单词形成的最大对数。

请注意,每个字符串最多可以属于一对。

示例1:
输入:单词= [“ CD”,“ AC”,“ DC”,“ CA”,“ ZZ”]

输出:2
说明:在此示例中,我们可以通过以下方式形成2对字符串:

  • 我们将0个字符串与第二字符串配对,因为词[0]的反向字符串为“ dc”,并且等于单词[2]。
  • 我们将第一个字符串与第三字符串配对,因为词[1]的反向字符串为“ ca”,并且等于单词[3]。 可以证明2是可以形成的最大对数。

示例2:
输入:单词= [“ ab”,“ ba”,“ cc”]

输出:1
说明:在此示例中,我们可以通过以下方式形成1对字符串:

  • 我们将0th字符串与第一个字符串配对,因为反向字符串[1]为“ ab”,并且等于单词[0]。 可以证明1是可以形成的最大对数。

示例3:
输入:单词= [“ AA”,“ AB”]

输出:0
说明:在此示例中,我们无法形成任何一对字符串。

约束:

1 <= word.length <= 50
单词[i] .length == 2
单词由不同的字符串组成。
单词[i]仅包含小写英文字母。

在这里,完成此操作的一种方法将是两个迭代,第一个通过每个单词。

class Solution {
    public int maximumNumberOfStringPairs(String[] words) {
        int maxPairs = 0;

        for(int i=0;i<words.length;i++){
            final String word = words[i];
            final String wordReversed = word.charAt(1) + "" +  word.charAt(0);

            for(int j=(i+1);j<words.length;j++){
                if(words[j].equals(wordReversed)) {
                    maxPairs++;
                }
            }
        }

        return maxPairs;
    }
}

运行时:8毫秒,比Java在线提交的27.17%更快地找到字符串对数。

内存使用量:42.3 MB,少于Java在线提交的75.70%以找到最大的字符串对数。

提供更好性能的一种方法是,而不是使字符串的实例和参考立即进行比较:

class Solution {
    public int maximumNumberOfStringPairs(String[] words) {
        int maxPairs = 0;

        for(int i=0;i<words.length;i++){
            for(int j=(i+1);j<words.length;j++){
                if(words[i].charAt(0) == words[j].charAt(1) && words[i].charAt(1) == words[j].charAt(0)) {
                    maxPairs++;
                }
            }
        }

        return maxPairs;
    }
}

运行时:1 ms,比Java在线提交的100.00%更快地找到字符串对数。

内存用法:41.6 MB,少于Java在线提交的79.74%的弦乐数量。

更简单,更快,直至点,如果要使它更可读,则可以用更多解释过程的方法替换条件。


就是这样!如果还有其他事情要讨论,请随时发表评论,如果我错过了任何事情,请告诉我,以便我可以相应地更新。

直到下一篇文章! :)