/**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   * 
   * @param str string字符串 
   * @param pattern string字符串 
   * @return bool布尔型
   */
  public boolean match (String str, String pattern) {
      // 加上空串，0~n
      boolean[][] dp = new boolean[str.length()+1][pattern.length()+1];
      // 两个都是空串
      dp[0][0] = true;
      // 字符串为空，正则表达式不为空
      for (int i = 2; i < dp[0].length; ++i){
          // 正则表达式从下标0开始
          if (pattern.charAt(i-1) == '*'){
              // 从下标1开始
              dp[0][i] = dp[0][i-2];
          }
      }
      // 状态转移
      for (int i = 1;i < dp.length;++i){
          for (int j = 1;j < dp[0].length;++j){
              if (pattern.charAt(j-1) != '*'){
                  if (pattern.charAt(j-1) == '.' || 
                      pattern.charAt(j-1) == str.charAt(i-1)){
                      dp[i][j] = dp[i-1][j-1];
                  }
              }else if (j >= 2 && pattern.charAt(j - 1) == '*'){
                  // 对于包含 * 的匹配
                  // 当前一位为 '.', 或者字符相等,则匹配
                  if (pattern.charAt(j - 2) == '.' ||
                      pattern.charAt(j - 2) == str.charAt(i - 1)) {
                      dp[i][j] = dp[i][j - 2] ||
                          dp[i - 1][j - 2] ||
                          dp[i - 1][j];
                  } else {
                      // 否则只能不匹配
                      dp[i][j] = dp[i][j - 2];
                  }
              }
          }
      }
      return dp[str.length()][pattern.length()];
  }