TSC3.13收到批准通知3.20通知寄卡 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>EB23 - 劳工卡

TSC3.13收到批准通知3.20通知寄卡

TSC3.13收到批准通知3.20通知寄卡# EB23 - 劳工卡

t*a2015-03-20 07:03

1 楼

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).
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
Given two sets of strings A and B,
Problem 1:
to find out a wildcard pattern w. w can match all strings in A but none
string in B. it w doesn't exist, return false.
Problem 2:
to find a group of wildcard pattern W={w_i}, W can match all strings in A
but none string in B. Minimize the size of W.

l*y2015-03-20 07:03

2 楼

【以下文字转载自 Travel 讨论区】
发信人: luckyhusky (luckyhusky), 信区: Travel
标题: UA里程换国航的改签问题
发信站: BBS 未名空间站 (Thu Apr 17 13:33:50 2014, 美东)
我在UA涨价之前换的里程，从中国飞美国的往返。
现在由于家里的原因，想改一下国内起飞的城市，原来是从广州飞北京然后飞Houston
，现在想改成从哈尔滨飞北京然后再飞Houston，或者直接把广州飞北京那段去掉。
我给UA打电话，转成中文的客服说是看不到票没法改（看不到有哈尔滨到北京的票），
但是我在网上是看到有票的，客
服解释说改签和重新订票看到的票不太一样……
想问下我现在需要换个时间重新打UA的电话吗？

A*D2015-03-20 07:03

3 楼

版上有几位同修有类似问题，标题作答一下吧
我上周五下午5点准时收到邮件说批准了
今天1：30am收到邮件说今天寄卡出来
从收到通知到寄出卡差不多5个工作日
比ead慢很多啊，ead隔天就寄出卡了

b*m2015-03-20 07:03

4 楼

这题有些意思。

e*n2015-03-20 07:03

5 楼

你网上自己改不就得了

s*52015-03-20 07:03

6 楼

恭喜了！

A*i2015-03-20 07:03

7 楼

DFA可用否？

l*82015-03-20 07:03

8 楼

国际航班不能自己改。把conformation #报给客服就应该能找到的。

r*z2015-03-20 07:03

9 楼

Congrats!

l*i2015-03-20 07:03

10 楼

problem 1 is easy, just make a DFA that recognizes only the strings in A,
and reject all other strings. Then your job is to wrong a regex to recognize
the same language as that DFA. Theoretically it is doable, although might
not be easy.

e*n2015-03-20 07:03

11 楼

我2月份就自己在ua网站上改得

国际航班不能自己改。把conformation #报给客服就应该能找到的。

【在 l****8 的大作中提到】

: 国际航班不能自己改。把conformation #报给客服就应该能找到的。

s*p2015-03-20 07:03

12 楼

恭喜

b*m2015-03-20 07:03

13 楼

神马是DFA呀？

D*s2015-03-20 07:03

14 楼

出票24小时之内？

【在 e*********n 的大作中提到】

: 我2月份就自己在ua网站上改得
:
: 国际航班不能自己改。把conformation #报给客服就应该能找到的。

w*22015-03-20 07:03

15 楼

Cong

m*k2015-03-20 07:03

16 楼

这题很复杂
谁有好办法，我要好好学习一下

【在 t****a 的大作中提到】

: 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).
: Some examples:
: isMatch("aa","a") → false
: isMatch("aa","aa") → true
: isMatch("aaa","aa") → false
: isMatch("aa", "*") → true
: isMatch("aa", "a*") → true

e*n2015-03-20 07:03

17 楼

出票一个多月了都，因为回国往后推了一周

出票24小时之内？

【在 D***s 的大作中提到】

: 出票24小时之内？

a*i2015-03-20 07:03

18 楼

恭喜

【在 A****D 的大作中提到】

: 版上有几位同修有类似问题，标题作答一下吧
: 我上周五下午5点准时收到邮件说批准了
: 今天1：30am收到邮件说今天寄卡出来
: 从收到通知到寄出卡差不多5个工作日
: 比ead慢很多啊，ead隔天就寄出卡了

f*e2015-03-20 07:03

19 楼

deterministic finite automata?

【在 b***m 的大作中提到】

: 神马是DFA呀？

l*y2015-03-20 07:03

20 楼

谢谢大家，客服找得到我的票，但是找不到哈尔滨到北京然后到Houston的票，所以没
法改，不知道是不是由于UA里程涨价的缘故……
我首先就是想着在网上改的，但是change flight它说united cannot initiate the
tickets，然后让我给UA打电话。
订票的时候就是一堆麻烦，客服看到的票价比我看到的要贵10，000里程，最后还是我
在网上刷了半天总算刷出来票然后自己订上的……

f*e2015-03-20 07:03

21 楼

find,grep源码maybe works.

【在 m***k 的大作中提到】

: 这题很复杂
: 谁有好办法，我要好好学习一下

j*y2015-03-20 07:03

22 楼

现在里程涨了，是不是主动改票应按新里程计算？

k*r2015-03-20 07:03

23 楼

目测的话，我想用recursive＋backtrack
分情况的, 我简单写了下，请指正
bool matchwords(char* word1, char* word2, int index1, int index2) {
if (index1 == strlen(word1)&& index2 == strlen(word2)) return true;
else {
if (word2[index2] == '*') {
if (matchwords(word1, word2, index1+1, index2+1)) return true;
else if (matchwords(word1, word2, index1+1, index2)) return true;
else if (word2[index2] == '?') {
return matchwords(word1, word2, index1+1, index2+1);
else {
if (word1[index1]== word2[index2] )
return matchwords(word1, word2, index1+1, index2+1);
else return false;
}
}
}

t*a2015-03-20 07:03

24 楼

这道题目和leetcode上的那题不同。请再看一遍题目？
另外，对leetcode的题目而言，你这个解法好像也不正确；同时，计算量也是指数的。
你确定这个解法通过了测试数据集得到正确结果了么？

true;

【在 k****r 的大作中提到】

: 目测的话，我想用recursive＋backtrack
: 分情况的, 我简单写了下，请指正
: bool matchwords(char* word1, char* word2, int index1, int index2) {
: if (index1 == strlen(word1)&& index2 == strlen(word2)) return true;
: else {
: if (word2[index2] == '*') {
: if (matchwords(word1, word2, index1+1, index2+1)) return true;
: else if (matchwords(word1, word2, index1+1, index2)) return true;
: else if (word2[index2] == '?') {
: return matchwords(word1, word2, index1+1, index2+1);

k*r2015-03-20 07:03

25 楼

哦，我又看了一遍，发现我只是在做ismatch 这个函数，
我的解法确实是指数级别的，没有考虑用dp做，
leetcode好久没做了，回头看看去：）

【在 t****a 的大作中提到】

: 这道题目和leetcode上的那题不同。请再看一遍题目？
: 另外，对leetcode的题目而言，你这个解法好像也不正确；同时，计算量也是指数的。
: 你确定这个解法通过了测试数据集得到正确结果了么？
:
: true;

t*a2015-03-20 07:03

26 楼

F*92015-03-20 07:03

27 楼

bool isMatch(const char *content, const char *pattern) {
if(content == NULL) {
if(pattern == NULL) {
return true;
} else {
return false;
}
}
if(*pattern == '*' && *(pattern+1) == '\0') { // *
return true;
} else if(*content == '\0') {
if(*pattern == '\0') {
return true;
} else {
return false;
}
} else if(*pattern == '?') { //?
if(*(pattern+1) == '*') { //?*
pattern += 2;
while(*content != '\0') {
while(*content != *pattern) {
++content;
}
if(isMatch(content, pattern)) {
return true;
} else { // skip failed match, move on
++content;
continue;
}
}
} else {
return isMatch(content+1, pattern+1);
}
} else if(*content ==*pattern) { // char = char
if(*(pattern+1) == '*') {
while(*content == *pattern) {
++content;
}
return isMatch(content, pattern+2);
} else {
return isMatch(content+1, pattern+1);
}
}
return false;
}

t*a2015-03-20 07:03

28 楼

继续顶，没人能搞定么？

c*t2015-03-20 07:03

29 楼

与leetcode regular expression matching那题思路不一样吗？

【在 t****a 的大作中提到】

t*a2015-03-20 07:03

30 楼

和那个题目不一样啊，难点在下面的Problem1和Problem2

【在 c********t 的大作中提到】

: 与leetcode regular expression matching那题思路不一样吗？

b*22015-03-20 07:03

31 楼

去年还真做过这道题：
private static boolean match(String regEx, String word) {
// TODO Auto-generated method stub
if(regEx == "*")
return true;
int reIndex = 0;
int wdIndex = 0;
for(;reIndexif(regEx.charAt(reIndex)==word.charAt(wdIndex)){
continue;
}else if(regEx.charAt(reIndex)!='?'&®Ex.charAt(reIndex)!='*'){
//simply not equivalent
return false;
}else if(regEx.charAt(reIndex)=='?'){
//deal with ?
//goto the next char
continue;
}else{
//deal with *
if(reIndex+1==regEx.length()) {
//this * is the very last one
return true;
}
boolean flag = false;
for(int i=0; wdIndex+iint j=0;
//check whether the following is * also
for(; reIndex+jif(regEx.charAt(reIndex+j)!='*') {
break;
}
}
if(reIndex+j==regEx.length()){
//this if checks whether it is like "abc***"
return true;
}else{
if(regEx.charAt(reIndex+j) == word.charAt(wdIndex+i)
|| regEx.charAt(reIndex+j) == '?'){
flag = flag||match(regEx.substring(reIndex+j),word.substring(wdIndex+
i));
}
}
}
return flag;
}
}
if(reIndex==regEx.length()&&wdIndex==word.length())
return true;
else
return false;
}

b*22015-03-20 07:03

32 楼

当时的全部测试：
match("*","abc") //true
match("*c","abc") //true
match("*a","abc") //false
match("a*","abc") //true
match("a?","abc") //false
match("ab?","abc") //true
match("a?c","abc") //true
match("*bc","abcbc") //true
match("a*b*c","abc") //true

match("*","") //true
match("*a","bac") //false
match("a*b","ab") //true
match("a?b","ab") //false
match("a**bc","acbc") //true
match("a*?bc","abc") //false
match("a**?**?bc","acbc") //false
match("a**?**?bc","accbc") //true