ARTS 第7周 动态规划

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).

public boolean isMatch(String s, String p) {

    boolean[][] match = new boolean[s.length() + 1][p.length() + 1];
    match[0][0] = true;

    // 初始化空串的匹配。
    for (int i = 1; i <= p.length(); i++) {
        if (p.charAt(i - 1) == '*') {
            match[0][i] = match[0][i - 1];
        }
    }

    for (int i = 1; i <= s.length(); i++) {
        for (int j = 1; j <= p.length(); j++) {
            if (p.charAt(j - 1) != '*') {
                match[i][j] = match[i - 1][j - 1] && (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1));
            } else {
                match[i][j] = match[i][j - 1] || match[i - 1][j];
            }
        }
    }
    return match[s.length()][p.length()];
}

Creating a unique, repeatable identifier for a URL

62⁷ = 3,521,614,606,208 urls
62⁸ = 218,340,105,584,896 urls
62⁹ = 13,537,086,546,263,552 urls
62¹⁰ = 839,299,365,868,340,224 urls
62¹¹ = 52,036,560,683,837,093,888 urls

private static final char[] corpus   = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789".toCharArray();
/*
* 通过输入一个数字种子，返回该种子对应的Base62字符串。种子不同的情况下可以保证不会重复
*/
public static final String getBase62From10(final long seed)
{
  String number = seed + "";
  char[] buf = new char[number.length()];
  int charPos = number.length() - 1;
  BigInteger bigIntegerNumber = new BigInteger(number);
  BigInteger radix = BigInteger.valueOf(62);

  while (bigIntegerNumber.compareTo(radix) >= 0)
  {
   buf[charPos--] = corpus[bigIntegerNumber.mod(radix).intValue()];
   bigIntegerNumber = bigIntegerNumber.divide(radix);
  }
  buf[charPos] = corpus[bigIntegerNumber.intValue()];
  return new String(buf, charPos, (number.length() - charPos));
}
/**
* 将一个62进制的整数转换为10进制的整数。
*/
public static final String getBase10From62(final long longNumber)
{
  String number = longNumber + "";
  BigInteger value = BigInteger.ZERO;
  for (char c : number.toCharArray())
  {
    value = value.multiply(BigInteger.valueOf(62));
    if ('0' <= c && c <= '9')
    {
      value = value.add(BigInteger.valueOf(c - '0'));
    }
    if ('a' <= c && c <= 'z')
    {
      value = value.add(BigInteger.valueOf(c - 'a' + 10));
    }
    if ('A' <= c && c <= 'Z')
    {
      value = value.add(BigInteger.valueOf(c - 'A' + 36));
    }
   }
   return value.toString();
}