StudentAttendanceRecordI [source code]

public class StudentAttendanceRecordI {
    public boolean checkRecord(String s) {
        char[] chars = s.toCharArray();
        int countA = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == 'A') {
                countA++;
                if (countA > 1) return false;
            } else if (chars[i] == 'L') {
                if (i + 1 < chars.length && chars[i + 1] == 'L') {
                    if (i + 2 < chars.length && chars[i + 2] == 'L') return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        StudentAttendanceRecordI tester = new StudentAttendanceRecordI();
        String i1 = "PPALLL";
        System.out.println(tester.checkRecord(i1));
    }
}

这里稍微有一个小的 beartrap 就是在向前伸脚(one step forward)的操作的过程中, 忘记了边界检查. 以后碰到这种探路型的题目, 要记得提醒自己这个问题.

if (i + 1 < chars.length && chars[i + 1] == 'L')

这个问题其实 debug 的时候还花了一点时间, 主要题目这句话表达的有点理解不清:

doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late)
刚开始我以为的是不能出现两个LL这样的, 比如LLPLLPLL这种应该算 false. 不过后来跑了几个 OJ 的 case, 发现这里表达的意思其实是连续出现的 L 的 run 的最大长度不能超过2.

最后的速度是: 8(95), 可以算是 submission 最优解了, 有点意外.
这里其实真正用到的优化也就有一个premature exit. 这个题目比较蠢的做法就是先1pass 过一遍然后再来判断 counter 什么的. 这个题目明显是可以 linear 的, 所以你现在要做的就是怎么做到 sublinear.
同样的, 你不需要判断the longest length of L run, 而是你只要判断是否存在长度为3的 run 就行了.

感觉 Google 的题目对于这种小细节, 无论是边界条件的检查, 还是小细节上的优化, 考察的比较多, 以后如果专门准备的时候要长一个心眼.

这里我处理 run 的思路相对来说依赖探路, 其实还有一个思路, 就是用一个 counter. 比如每当碰到 L, counter++, 然后检查 counter 不超过3; 每当碰到其他, count = 0.

这个是 editorial 里面给出的另外一个思路:

s.indexOf("LLL")<0;

这样就只要count A就行了;

discussion对于这个依赖 API 的做法给出了另外一个思路:

public class Solution {  
    public boolean checkRecord(String s) {  
        if(s.indexOf("A") != s.lastIndexOf("A") || s.contains("LLL"))  
            return false;  
        return true;  
    }  
}

从学习 API 的角度来说, 还是好过没有的.

editorial给出的另外一个利用 regex 的思路是:

public class Solution {  
    public boolean checkRecord(String s) {  
        return !s.matches(".*(A.*A|LLL).*");  
    }  
}

这题这里要求的这个 regex 好像并不是特别复杂.

这个是后来想到的一个小优化:

public class Solution {  
    public boolean checkRecord(String s) {  
        char[] chars = s.toCharArray();  
        int countA = 0;  
        for (int i = 0; i < chars.length;) {  
            if (chars[i] == 'A') {  
                countA++;  
                if (countA > 1) return false;  
                i++;  
            } else if (chars[i] == 'L') {  
                if (i + 1 < chars.length && chars[i + 1] == 'L') {  
                    if (i + 2 < chars.length && chars[i + 2] == 'L') return false;  
                    i += 2;  
                }  
                else i++;  
            } else i++;  
        }  
        return true;  
    }  
}

结果最后速度还是降低到了9, 有点奇怪. 这个优化的本意是可以如果出现长度为2的 run, 可以跳过下一个 iteration.
不过跟前面最优的8其实差距也只有1, 估计就是 OJ 的波动.

Problem Description

You are given a string representing an attendance record for a student. The record only contains the following three characters:

'A' : Absent.
'L' : Late.
'P' : Present.
A student could be rewarded if his attendance record doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late).

You need to return whether the student could be rewarded according to his attendance record.

Example 1:
Input: "PPALLP"
Output: True
Example 2:
Input: "PPALLL"
Output: False
Difficulty:Easy
Category:Algorithms
Acceptance:43.57%
Contributor: fallcreek
Companies
google
Related Topics
string
Similar Questions
Student Attendance Record II