LeetCode刷题笔记 - JavaScript（四）

剑指 Offer 37. 序列化二叉树
剑指 Offer 19. 正则表达式匹配 LCOF

1.剑指 Offer 37. 序列化二叉树

请实现两个函数分别用来序列化和反序列化二叉树。
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

题目大意模拟二叉树的序列化和反序列化。

解题思路dfs的序列化和反序列化。

代码

var serialize = function(root, str='') {
    if(root === null) {
        str += 'null,';
        return str;
    } else {
        str += root.val + ',';
        str += serialize(root.left);
        str += serialize(root.right); 
    }
    return str;
};

function dfs(data) {
    if(data[0] == 'null') {
        data.shift();
        return null;
    }
    const root = new TreeNode(data[0]);
    data.shift();
    root.left = dfs(data);
    root.right = dfs(data);
    return root;
}

var deserialize = function(data, idx = 0) {
    data = data.split(',');
    return dfs(data);
};

1.剑指 Offer 19. 正则表达式匹配

请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符而’'表示它前面的字符可以出现任意次（含0次。在本题中匹配是指字符串的所有字符匹配整个模式。例如字符串"aaa"与模式"a.a"和"abaca"匹配但与"aa.a"和"ab*a"均不匹配。

题目大意给出包含通配符的正则表达式判断是否与测试字符串匹配。

解题思路递归。首先判断首位字符是否相同。如果相同继续判断后面是否还有*通配符如果有分别判断匹配n次和匹配0次的情况。

代码

var isMatch = function(s, p) {
    if(p.length === 0) return s.length === 0;
    const flag = s.length !== 0 && (s[0] === p[0] || p[0] === '.');
    if(p.length >=2 && p[1] === '*') {
    	// *匹配一个 || *匹配0个
        return (flag && isMatch(s.slice(1),p)) || isMatch(s,p.slice(2));
    } else {
        return flag && isMatch(s.slice(1), p.slice(1));
    }
};