【D30】反转链表&正则表达式匹配 （LC 206&10 ）

206. 反转链表

问题描述

反转一个单链表。

解题思路1-迭代法

1）定义指向前一个节点的指针prev，初始值为空
2）遍历链表，将每个节点的next指针指向前驱节点。每次迭代过程如下：

• 定义临时变量temp，用于保存当前节点的后继节点

  
  step 1

• 将当前节点的next指针指向前驱节点

  
  step 2

• 当前节点成为下一个节点的前驱节点

  
  step 3

• temp中的后继节点成为下一个当前节点

  
  step 4

代码实现1-迭代法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while(head != null){
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        } 
        return prev;
    }
}

• 时间复杂度O(n)
• 空间复杂度O(1)

解题思路2-递归法

边界情况：链表为空或者链表中只有一个结点（head == null || head.next == null）
递归函数实现功能：反转链表找到newHead
递归参数：head.next
递归执行内容：
head.next.next = head; //（对应图中节点2的next指向1）
head.next=null; //（对应图中节点1的next指向空）

image.png

代码实现2-递归法

class Solution {
    public ListNode reverseList(ListNode head) {
        while(head == null || head.next == null){
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

• 时间复杂度O(n)
• 空间复杂度O(n)，使用递归会使用隐式栈空间。递归深度可能会达到 nn 层。

10. 正则表达式匹配

问题描述

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

• '.' 匹配任意单个字符
• '*' 匹配零个或多个前面的那一个元素
• 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

解题思路

采用动态规划解题。

• dp数组：dp[i][j]表示s中前i个字符和p中前j个字符能匹配
• base case：分为三种情况。
  （1）s和p都为空串：一定能匹配
  （2）s不为空，p为空：一定不能匹配
  （3）s为空，p不为空：模式串为字母和*间隔排列且长度为偶数时（如，*a*a*a*b*）能够匹配空串，其他的是都是false。
• 状态转移
  （1）如果p[j] != '*' , 则看s中第i个字符和p中第j个字符能否匹配。若不能匹配则dp[i][j] == false ；若能匹配则取决dp[i-1[j-1]的值。
  （2）如果p[j] == '*' ,则看s中第i个字符和p中第j - 1个字符能否匹配。若不能匹配，则取决于dp[i][j-2]的值（没有匹配，模式串中的a*被当作空串）；若能匹配，则可能有三种情况dp[i][j] = dp[i-1][j] || dp[i][j - 1]|| dp[i][j - 2]：

// = dp[i-1][j]，多个字符匹配，模式串中的a*被当作aa...
// = dp[i][j-1]，单个字符匹配，模式串中的a*被当作a
// = dp[i][j-2]，没有匹配, 模式串中的a*被当作空串

代码实现

class Solution {
    public boolean isMatch(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        //dp[i][j]表示s中前i个字符和p中前j个字符能匹配
        boolean[][] dp = new boolean[sLen + 1][pLen + 1];

        //base case
        // 1.两个空串能够匹配
        dp[0][0] = true;
        // 2.如果s不为空, p为空，则一定不能匹配
        for(int i = 1; i <= sLen; i++) {
            dp[i][0] = false;
        }
        // 3.如果s为空, p不为空，*a*a*a*a*这种能够匹配空串，其他的是都是false。
        //  奇数位不管什么字符都是false，偶数位为* 时则: dp[0][j] = dp[0][j - 2]
        for(int j = 1; j <= pLen ; j++) {
            if(j % 2 == 0 && p.charAt(j - 1) == '*'){
                dp[0][j] = dp[0][j - 2];
            }else{
                dp[0][j] = false;
            }  
        }
        
        for(int i = 1; i <= sLen; i++){
            //si表示s中的第i个字符
            char si = s.charAt(i - 1);

            for(int j = 1; j <= pLen; j++){
                if(p.charAt(j - 1) != '*'){
                    dp[i][j] = dp[i - 1][j - 1] && match(si, p.charAt(j - 1));
                }else {
                    if(match(si, p.charAt(j - 2))){
                        //dp[i-1][j]，多个字符匹配，模式串中的a*被当作aa... 
                        //dp[i][j-1]，单个字符匹配，模式串中的a*被当作a
                        //dp[i][j-2], 没有匹配, 模式串中的a*被当作空串
                        dp[i][j] = dp[i-1][j] || dp[i][j - 1]|| dp[i][j - 2]; 
                    }else {
                        //没有匹配，模式串中的a*被当作空串
                        dp[i][j] = dp[i][j-2];
                    }
                }
            }
        }
        return dp[sLen][pLen];
    }

    //判断两个字符是否能够匹配
    public boolean match(char s, char p){
        if(p == '.' || s == p){
            return true;
        }
        return false;
    }
}