求字符串中第一个只出现一次的字符

大家好, 这里是K字的研究. 今天又是Java101系列,继续玩儿字符串.

求一个字符串只出现了一次的字符中的第一个

题目有点绕, 是这样, 比如有个字符串 “abcdefba”. 明显,c,d,e,f都只出现了一次. 但是c靠前, 这里要的c.

怎么做呢? 普通思路是这样的,从前到后,扫描字符串,用一个HashMap记录每个字符出现的位置,当发现map里已经记录过了, 就把这个字符拉黑. 最后,把map里没被拉黑的值里, 取最小的.

普通版

String s = "abcdefba";

HashMap<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
  char c = s.charAt(i);
  map.put(c, map.containsKey(c) ? -1 : i);
}
Character key = map.entrySet()
    .stream().filter(e -> e.getValue() >= 0)
    .min(Comparator.comparingInt(Map.Entry::getValue))
    .get().getKey();
System.out.println("min = " + key);
//min = c

这个版本, 简单,直白,好理解. 但是, 如果真的熟悉Java的话, 这个其实有一个更神奇的写法.

神奇版

遍历完字符串以后, 后面找到具体字符的操作,太重了. 完全没必要. 本质原因是, HashMap是无序的.如果Map能按照插入顺序排列的话, 这里面根本没这么麻烦.

嗯,有的. Java有一个可以保证插入顺序的Map实现,LinkedHashMap. 利用LinkedHashMap的特性, 这个代码可以改写为这样

 String s = "abcdefba";

HashMap<Character, Integer> map = new LinkedHashMap<>();
for (Character c : s.toCharArray()) {
  map.compute(c, (k, v) -> v == null ? 1 : ++v);
}
Character key = null;
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
  if (entry.getValue() == 1) {
    key = entry.getKey();
    break;
  }
}
System.out.println("min = " + key);

合理利用LinkedHashMap的特性, 这里简化了不少.

Stream+LinkedHashMap版

String s = "abcdefba";
Character key = s.chars().mapToObj(c -> (char) c)
    .collect(Collectors.groupingBy(Function.identity()
        , LinkedHashMap::new
        , Collectors.counting()))
    .entrySet().stream()
    .filter(e -> e.getValue() == 1)
    .map(Map.Entry::getKey)
    .findFirst().get();
System.out.println("min = " + key);

有时候,代码用了Stream其实也不好. 这种一句版,不熟悉话挺难看懂的.Collectors.groupingBy(Function.identity() , LinkedHashMap::new , Collectors.counting())这句用了个特殊语法, 给Collectors提供了一个Map Supplier.

找到字符串的最长公共前缀

输入: [“A study in K”,”A study in Scarlet”,”A stupid problem”] 输出: “A stu”

普通写法是这样的

从前往后循环, 比较每一位上的所有char.遇到不一致break出来

String[] input = new String[]{"A study in K", "A study in Scarlet", "A stupid problem"};
int i = 0;
label:
while (true) {
  Character lastC = null;
  for (String s : input) {
    if (i == s.length()) break label;
    char c = s.charAt(i);
    if (lastC == null) lastC = c;
    else if (c != lastC) {
      break label;
    }
  }
  i++;
}
System.out.println(input[0].substring(0, i));

用到了我们的老朋友, 跳出双层循环时候必备神器, label. 这个label其实随便写什么都行. 甚至这个代码写成:

http://afk.now.sh
while (true) {
  break http;
}

这个样子都可以.

文艺版本

这个写法,不是特别的优雅. 这里其实可以考虑使用二分搜索.

比如, 我们可以先找到最短的字符串.. 直接去看他是不是其他字符串的前缀. 如果是,返回.不是, 字符串折半,再检测一次. 来实现一下这个代码.

String[] input = new String[]{"A study in K", "A study in Scarlet", "A stupid problem"};
int right = Arrays.stream(input).mapToInt(x -> x.length()).min().getAsInt();
int left = 0;

while (left < right) {
  int mid = (left + right) / 2;
  String test = input[0].substring(0, mid + 1);
  boolean allMatch = true;
  for (String s : input) {
    if (!s.startsWith(test)) {
      right = mid - 1;
      allMatch = false;
      break;
    }
  }
  if (allMatch) left = mid + 1;
}
System.out.println(input[0].substring(0, (left + right) / 2));

写法大致如此, 不过有点粗犷.

前缀树版

关于公关前缀,其实还有另一种解法, Trie. Trie树也叫前缀树,一个节点的所有后继都有相同的前缀，用来做这个刚刚好.

他的节点有些特殊.

一个单根root
每个节点一个字符
每个节点有多个指向子节点们的引用
节点有一个boolean属性表示在这里是否结束了一个字符串

比如我们这个输入, 为了方便,去掉空格变成.{"AstudyinK", "AstudyinS", "Astupidp"}按照添加顺序,可以build成这样. false我就不画了,只画true.

加上第二个串以后, 变成这样.

加上第三个串以后, 变成这样

这图就很明显了,我们能一眼看出来, 分叉的地方,就是公关前缀结束的地方.

我们实现一下这个数据结构, 用来做这个题目.

节点定义

public static class Node {
    boolean flag = false;
    Map<Character, Node> children;
}

这里偷了个懒, 字符其实存在Map里了.

Trie树残废版

public static class Trie {
    Node root = new Node();

    public void insert(String s) {
        Node node = this.root;
        for (char c : s.toCharArray()) {
            if (node.children == null) node.children = new HashMap<>();
            node = node.children.computeIfAbsent(c, k -> new Node());
        }
        node.flag = true;
    }
}

这里是残废版本, 完整的trie要支持增删查的. 这个场景只要新增就可以了.

使用

String[] input = new String[]{"A study in K", "A study in Scarlet", "A stupid problem"};
Trie trie = new Trie();
Arrays.stream(input).forEach(trie::insert);
Node node = trie.root;
int i = 0;
while (node.children.size() == 1) {
  node = node.children.values().iterator().next();
  i++;
}
System.out.println(input[0].substring(0, i));