First Unique Character in a String (找到一个字符串中第一个不重复的字符)

问题描述

下面是有关这个问题的描述部分。

英文

Given a string s, return the first non-repeating character in it and return its index. If it does not exist, return -1.

中文

针对给定的一个字符串 s,你需要写一个算法,返回给定字符串中不重复字符的位置(index),如果所有的字符在给定的字符串中都有重复的话,那么你应该返回 -1。

样例

下面给出了这个问题的示例,以便于你参考。

Input: s = “comossez” 0
Input: s = “lovelycomossez” 2
Input: s = “aabb” -1

思路点评和源代码

整体来说这个题目的难度并不大。

有很多种解题的思路,首先你需要把字符串拆开放到数组中,这样你才能够一个字符一个字符的进行遍历。

我的这个思路肯定不是效率最高的,我的思路就是将字符串放到数组中,然后对数组进行遍历,在这个过程的同时还定义一个 Map,在这个 Map 中存储的 Key 就是正在查找的字符串,如果当前字符串在 Map 中没有的话,就 Put 进去。

Put 进行的 Key 是当前的字符串,值是当前字符串所在数组的下标。

如果当前字符串已经在 Map 中有的了话,我们可以修改 Map 的值为 2#5 这样的方式,中间可以使用 # 号或者任意特殊字符。

当完成上面的遍历后,我们就获得了需要的 map 了。

然后再对 Map 进行遍历,找到第一个不含有 # 号的值就行了。

为了进行有序存储,我们需要使用 LinkedHashMap,因为 HashMap 是无序的,无序的 Map 会把找到第一个的输入顺序弄错。

上图是对内存进行分析后,可以看到初始化后的 Map 的值。

代码

请访问 GitHub:java-tutorials/LeetCode0387FirstUniqueCharacterTest.java at master · cwiki-us-docs/java-tutorials · GitHub

这个题目在随后的面试中又出来变种。

这次需要函数返回的找到的字符串,同时输入的字符串中还有大小写。

另外,因为在线编译器的限制,你又不能使用 HashMap。

解题思路

使用 Java 来说还是相对比较好处理的。

解题思路也比较简单,你需要使用一个中间变量来存储,首先还是需要将进行处理的字符串转换为 char 的数组。

然后在数组中拿到第一个字符。

当你拿到第一个字符的时候,你做这样一件事情,将这个字符对目标字符串进行替换为 “”;

如果有相同的,那么肯定会被替换掉,同时你再考虑替换掉一次大写的,一次小写的。

如果有大写字母相同的,那么也会被替换掉。

例如字符串 “serTSSEr”,那么你在完成后上面的算法后,假设我们对比第一个要替换的字符是 s,那么完成后算法后的字符串为 “erTEr”。

我们发现字符串的长度就不是原始长度 -1 了,因为你替换了多个字符串,因此可以知道这个被查找的字符是重复的。

当我们循环到字符 T 的时候,我们会发现完成后算法后的字符串长度就是原始输入字符串长度 -1,那么我们就知道 T 就是我们需要输出的字符了。

需要注意的是特殊情况 “ssee” 这种情况,如果你循环到最后,可能会发现原始字符的长度和完成整个循环后字符的长度没有变化,那么说明所有的字符都有重复,那么你应该返回 “”。

更进一步

为了减少搜索次数,你可以在完成后第一次替换后的余下的字符串中进行算法查找和替换,因为这个算法只需要找到字符,并不需要你输出下标。

因此在循环中,下次需要查找的字符串长度就减少了,算法的效率也就更高了。

完整测试代码,请参考题目中的 GitHub 链接地址:java-tutorials/LeetCode0387FirstUniqueCharacterTest.java at master · cwiki-us-docs/java-tutorials · GitHub

我们这里将这个测试方法写在下面供需要的童鞋参考。

    /**
     * Return the first Uniq Char String without using Map
     * @param data
     * @return
     */
    private String firstUniqCharString(String data) {
        // NULL CHECK
        if (data.equals("")) {
            return "";
        }

        char[] strArray = data.toCharArray();
        String retStr = "";

        if (data.length() == 1) {
            retStr = data;
        }

        for (int i = 0; i < strArray.length; i++) {
            String valStr = Character.toString(strArray[i]);
            String rData = data;
            rData = data.replace(valStr, "");
            rData = rData.replace(valStr.toUpperCase(Locale.ROOT), "");
            rData = rData.replace(valStr.toLowerCase(Locale.ROOT), "");

            if (rData.length() == 0) {
                retStr = "";
            } else if (rData.length() + 1 == data.length()) {
                retStr = valStr;
                break;
            }
        }
        return retStr;
    }