以状态机的思想来解题

发表于 更新于

背景

今天在刷力扣的每日一题的时候，突然泵生出一个美妙的想法，遂做记录。题目如下：

检测大写字母

我们定义，在以下情况时，单词的大写用法是正确的：

  • 全部字母都是大写，比如 “USA” 。
  • 单词中所有字母都不是大写，比如 “leetcode” 。
  • 如果单词不只含有一个字母，只有首字母大写， 比如 “Google” 。

给你一个字符串 word 。如果大写用法正确，返回 true ；否则，返回 false 。

很简单的一道题目，基于模拟的方法其实就随便写了，但是如何引入状态机的思想，其实就可以深刻体会到代码之美！

状态机

基于题目背景，我们就可以开始构建我们的状态机了，首先引入一个初始状态初始(0)，当首字母分别为大写字母或是小写字母时，我们可以引入另外两个状态首字母大写(1)和首字母小写(3)(请忽略这里的状态编号，因为当时写的时候我没有编码，所以是画完状态转移图后再进行编码的:( )，此后，再根据下一位的大小写情况继续引入全部大写状态全体大写(2)，全体小写的状态其实可以与首字母小写进行合并，这里不做细推了。最后，得到我们大致的状态转移图如下：

状态转移图

整个状态机十分简单，带双环的表示接受状态，错误状态表示字符串非法，L(lower case)表示输入为小写字母，而U(upper case)表示大写字母，而且可以看到这是一个确定的有限状态自动机，我们可以直接以此来进行编码。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    /*
        一共五个状态（代码中隐含最后一个）:初始(0), 首字母大写(1), 全体大写(2), 全体小写(3), 错误(4)
     */
    public boolean detectCapitalUse(String word) {
        int state = 0;
        for (char c : word.toCharArray()) {
            boolean U = Character.isUpperCase(c);
            switch (state){
                case 0: state = U ? 1 : 3;break;
                case 1: state = U ? 2 : 3;break;
                case 2: if (!U) return false;break;
                case 3: if (U) return false;break;
            }
        }
        return true;
    }
}

思考与感受

自动机不愧为计算机科学的一个重大理论成果，它的精妙性与简洁性是无与伦比的，似乎包揽了世间万事万物的运作规律，如果抛离上述的自动机理论单看这份源代码，可能会觉得它简直莫名其妙，正确性更是无从谈起，可是它就是正确的！正是状态机的运作保持了这份逻辑！因此，在很多更加复杂问题中，我们如果也以这种思维角度去思考，或许能够大大地简化问题，从更加本质抽象的层面去看待问题。