1

我正在研究一个涉及字符串的非常常见的 Java 问题的解决方案。我想写一个方法来查看一个字符串是否是另一个的排列(字谜)。

我的解决方案是这样的:我正在编写一个需要两个字符串的方法。我遍历一个 String 并将找到的字符放入 HashMap 中,其中键是字母,值是该字母的出现次数,作为 int。一旦我完成了第一个字符串的迭代,我将迭代第二个字符串并递减在同一个 HashMap 中找到的每个字符的值。

一旦键达到零,我就从 HashMap 中完全删除键/值对。一旦我完成了对第二个字符串的迭代,我就只检查 HashMap 是否为空。如果是,那么这两个字符串是彼此的排列/字谜,否则该方法返回 false。

我的方法如下:

public boolean checkPermutation (String stringA, String stringB) {

        if (stringA.length() != stringB.length()) {

            return false;

        }

        else {


        HashMap alpha = new HashMap();

        for (int i = 0; i < stringA.length(); i++) {

            if (!alpha.containsKey(stringA.charAt(i))) {

                alpha.put(stringA.charAt(i), 0);
            }

            else {

                Integer value = (Integer) alpha.get(stringA.charAt(i));
                int newValue = value.intValue();
                alpha.put(stringA.charAt(i), newValue++);

            }

        }

        for (int j = 0; j < stringB.length(); j++) {

            if (alpha.containsKey(stringB.charAt(j))) {

                Integer value = (Integer) alpha.get(stringA.charAt(j));
                int newValue = value.intValue();//null pointer exception here

                if (newValue > 1) {

                    alpha.put(stringB.charAt(j), newValue--);

                }

                else {

                    alpha.remove(stringB.charAt(j));

                }

            }

        }

        if (alpha.isEmpty())
            return true;

        else
            return false;


        }
    }

我的问题是我的解决方案是区分大小写的(即如果我输入“Hello”和“oellH”,我会得到一个空指针异常)。我想让这个解决方案不区分大小写,并弄清楚为什么我得到一个空指针异常。谁能看到我做错了什么?

作为一个小的后续问题,尽管有两个 for 循环,但这种类型的解决方案是否为 O(n)?

4

2 回答 2

1
Integer value = (Integer) alpha.get(stringA.charAt(j));

尝试将 stringA 更改为 stringB。

Integer value = (Integer) alpha.get(stringB.charAt(j));

因为如果您提供不同的字符串,其中没有相同的字符,则该值将为空,并且它将通过 NPE。

将两个字符串都更改为小写或大写。

stringA= stringA.toLowercase();
stringB= stringB.toLowercase();
于 2013-02-18T05:09:45.160 回答
1

抛出空指针异常是因为您正在检查 hashmap 中 stringB 的 char,然后提取 stringA 的值,此时可能会从 hashmap 中删除该特定值,从而引发空指针错误。

如果你仔细调试你的代码

if (alpha.containsKey(stringB.charAt(j))) {
    Integer value = (Integer) alpha.get(stringA.charAt(j));
 ///Your code
}

将其更改为

if (alpha.containsKey(stringB.charAt(j))) {
    Integer value = (Integer) alpha.get(stringB.charAt(j));
///Your code
}

对于您的其他问题,使其不区分大小写,在开始操作之前将字符串都设为小写或大写

stringA = stringA.toLowerCase();
stringB = stringB.toLowerCase();
于 2013-02-18T05:24:01.097 回答