学会自顶向下编程

2020-4-6记

什么叫自顶向下编程？拿leetcode 125题 验证回文字符串进行举例：

//给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 
//
// 说明：本题中，我们将空字符串定义为有效的回文串。 
//
// 示例 1: 
//
// 输入: "A man, a plan, a canal: Panama"
//输出: true
// 
//
// 示例 2: 
//
// 输入: "race a car"
//输出: false
// 
// Related Topics 双指针 字符串

对于本题，假设我有这样的思路：

1. filter out number & character
2. reverse and compare

按照自顶向下的编程思想，我应该这样做：
首先，先确立好思路。我们需要先将数字和字母之外的字符过滤出去，然后反转。在java中有忽略大小写的比较方法equalsIgnoreCase。我们对过滤后的字符串与过滤反转后的字符串进行不区分大小写的比较就完成了本题。应用自顶向下的编程思想，我们应该先从整体的逻辑出发，先写出整体的逻辑，反转，过滤的函数先用字符串来代替。

class Solution {
    public boolean isPalindrome(String s) {
        // 1. filter out number & character
        String filteredS = _filterNonNumberAndChar(s);
        // 2. reverse and compare
        String reversedS = _reverseString(filteredS);
        return reversedS.equalsIgnoreCase(filteredS);
    }
}

然后再实现具体的功能,并做代码优化。

class Solution {
    public boolean isPalindrome(String s) {
       
        String filteredS = _filterNonNumberAndChar(s);

        return _reverseString(filteredS).equalsIgnoreCase(filteredS);
    }

    private String _reverseString(String s){
        return new StringBuilder(s).reverse().toString();
    }

    private String _filterNonNumberAndChar(String s){
        return s.replaceAll("[^A-Za-z0-9]","");
    }

}

本题这种方法自然不是最优解，不过这种自顶向下的编程思想是值得学习的。