J**9
发帖数: 835 | 1 char *hkStringRemoveADoubleB(char *str)
{
if (!str) return NULL;
char *s=str;
char *d=str;
int countb = 0;
int len=0;
while(*s)
{
if (*s=='B') countb++; /// Count B
if(*s!='A') /// Remove A
{
*d++=*s++;
len++;
}
else
s++;
}
if(len)
{
s = str+(len+countb); ///New string length
*s = '\0';
s--;
d--;
while(d!=str)
{
if (*d=='B... 阅读全帖 |
|
p*****2
发帖数: 21240 | 2 我写了一个练练
def count(str):
if not (str and len(str)):
return 0
l=len(str)
dp=[1]*2
if str[-1]=='0':
dp[1]=0
for i in xrange(2,l+1):
if str[-i]=='0':
dp[i%2]=0
else:
c=dp[(i+1)%2]
if str[l-i:l-i+2]<="26":
c+=dp[i%2]
dp[i%2]=c
return dp[l%2] |
|
s******k
发帖数: 3716 | 3 手快不需要５分钟
int getNumDecode(const char *str)
{
char temp[3]; temp[1] = temp[2] = '\0';
if(strlen(str) == 0) return 1;
int num = 0;
temp[0] = str[0];
if(mymap[temp)>0) // we have 1 digit decode a letter
num += getNumDecode(str+1);
if(strlen(str)==1) return num;
temp[1] = str[1];
if(mymap[temp]>0) // we have 2 digits decode a letter
num += str+2;
return num;
} |
|
z******e
发帖数: 82 | 4 -_-!!, what bad test skill I have.
for this test case, change
if (c == '"' && !slash2 && !slashstar) {
to
if (c == '"' && lastc != '\' && !slash2 && !slashstar) {
complete code:
private static String uncomment(String str) {
boolean slash2 = false;
boolean inStr = false;
boolean slashstar = false;
StringBuilder sb = new StringBuilder();
char lastc = ' ';
char c = ' ';
int deleteStart = -1;
for (int i = 0; i < str.length(); i++) {
... 阅读全帖 |
|
c********t
发帖数: 5706 | 5 能不能和下面解法对比一下优缺点？
public static void permutation(String str) {
permutation("", str);
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) System.out.println(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.
substring(i+1, n));
}
} |
|
c********t
发帖数: 5706 | 6 能不能和下面解法对比一下优缺点？
public static void permutation(String str) {
permutation("", str);
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) System.out.println(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.
substring(i+1, n));
}
} |
|
c********t
发帖数: 5706 | 7 void compose(String str, char ch) {
if (str == null || str.isEmpty())
return;
travel(ch, str.charAt(0));
System.out.print("output ");
for (int i = 1; i < str.length(); i++) {
travel(str.charAt(i - 1), str.charAt(i));
System.out.print("output ");
}
}
void travel(char a, char b) {
int i = (a - 'A') / 5, j = (a - 'A') % 5;
int m = (b - 'A') / 5, n = (b - 'A') % 5;
if (a == 'Z' && b != 'Z' && b != 'U') {
travel('Z', 'U');
tr... 阅读全帖 |
|
p*****p
发帖数: 379 | 8 试了一下
Length: 10
kitzyxacbh
string longestSubstringWithUniqueChar(string str) {
int i = 0, j = 0;
int start = 0, maxLen = 0;
hash_map charMap; // recent index of char
for (; j < str.size(); ++j) {
if (charMap.find(str[j]) != charMap.end()) {
int newStart = charMap[str[j]] + 1;
for (; i < newStart; ++i) {
charMap.erase(str[i]);
}
}
charMap[str[j]] = j;
if (j - i + 1 > maxLen) {
... 阅读全帖 |
|
c*******r
发帖数: 309 | 9 这下边的code我总觉得初始判断有问题， 如果str==null||str.length()==0返回null
这个recursion还有效么
public ArrayList permutes(String str){
if(str==null||str.length()==0)
return null;
ArrayList result=new ArrayList();
char first=str.charAt(0);
String other=str.substring(1);
ArrayList strings=permutes(other);
for(int i=0;i
for(int j=0;j
String temp=insert(s... 阅读全帖 |
|
w****a
发帖数: 710 | 10 感谢楼上的bless
我是根本没想到电面就开始考DP题，DP题我做了不超过10题。所以拿道题我也没敢用DP
做。怕写错，就用递归做了。给你们看看我做的吧。最后代码没啥问题，我刚刚跑了几
个测试都过了。
void maxSubwords(int subs, string& str, map& dict,int id, int &
maxNumber){
if(id == str.size()){
maxNumber = max(subs,maxNumber);
return;
}
for(int subStrBegin = id; subStrBegin < str.size(); subStrBegin ++){
bool canContinue = false;
for(int subStrEnd = subStrBegin ; subStrEnd < str.size(); subStrEnd
++){
string substring = st... 阅读全帖 |
|
f*******t
发帖数: 7549 | 11 public int ladderLength(String start, String end, HashSet dict) {
if (start == null || end == null || start.length() != end.length())
return 0;
int dist = 1;
HashSet used = new HashSet();
HashSet cur = new HashSet();
cur.add(start);
while(!cur.isEmpty()) {
HashSet newCur = new HashSet();
dist++;
for (String s : cur) {
char[] s... 阅读全帖 |
|
f*******t
发帖数: 7549 | 12 public int ladderLength(String start, String end, HashSet dict) {
if (start == null || end == null || start.length() != end.length())
return 0;
int dist = 1;
HashSet used = new HashSet();
HashSet cur = new HashSet();
cur.add(start);
while(!cur.isEmpty()) {
HashSet newCur = new HashSet();
dist++;
for (String s : cur) {
char[] s... 阅读全帖 |
|
c**1
发帖数: 71 | 13 here is the correct version:
int reverse_polish(const char*& str) {
if (is_number(str)) return parse_nuber(str);
OpCode op = getOpCode(str);
int x = reverse_polish(str);
int y = reverse_polish(str);
return op.apply(x,y);
}
note there is no error check, and note str is passed as reference to const
char*, so that functions can read what it needs as well as forwarding the
pointer. |
|
m**********e
发帖数: 22 | 14 DP:
public bool WordBreak(string str, Dictionary dict)
{
// f[i] is true when str[0,...,i] is word break;
// f[i] = true when f[k]==true and str[k+1,...,i] is a word
// or str[0,...,i] is a word
int n = str.Length;
bool[] allWords = new bool[n];
int i, j;
for (i = 0; i < n; ++i)
{
if (!allWords[i] && dict.ContainsKey(str.Substring(0, i + 1)
)... 阅读全帖 |
|
h**o
发帖数: 548 | 15 没见过这题。 我当时这样写的。
请问哪里有真确答案？
int countPattern(char* str, char pattern){
if(!str) return 0;
int sum = 0;
while(!(str+1) && *(str+1)!= 0){
sum += countByte(str, str+1, pattern);
str++;
}
return sum;
}
int countByte(char* str1, char* str2, char pattern){
int cnt = 0;
char ch;
for (int i = 0; i < 8; i++){
ch = str1<> (8-i);
if (ch ^ pattern==0) cnt++;
}
return cnt;
} |
|
g*****g
发帖数: 212 | 16 RF1:
从左到右扫描：
记录当前最大，
1）如果当前值小于最大， 删除最大
2）如果便利到最后，删除最大
int deleteOne(char[] str, int n)
{
if (n == 0)
return 0;
int j= 0;
for(int i=1; i
{
if (str[i]
{
break;
}
else if (str[i] > str[j])
{
i = j;
}
}
for(int k=j; k
{
str[k] = str[k+1]
}
return n-1;
} |
|
p*****2
发帖数: 21240 | 17 (def dict #{"cat", "cats", "and", "sand", "dog"})
(defn word-break [str]
(
(fn dfs [str, p, res]
(if (= p (count str))
(println res)
(loop [end (inc p)]
(when (<= end (count str))
(let [word (subs str p end)]
(when (contains? dict word)
(dfs str end (conj res word)))
(recur (inc end)))))))
str 0 []))
(word-break "catsanddog") |
|
p*****2
发帖数: 21240 | 18 来自主题: JobHunting版 - M的面试题 (defn word-break [str]
((fn dfs [str, p, res]
(if (= p (count str))
(println res)
(loop [end (inc p)]
(when (<= end (count str))
(let [word (subs str p end)]
(when (contains? dict word)
(dfs str end (conj res word)))
(recur (inc end)))))))
str 0 [])) |
|
w********s
发帖数: 1570 | 19 brute force多简单，复杂度
bool isPrefix(char* pattern, char* str, int size)
{
for (int i = 0; i < size && str[i] != '\0'; ++i)
{
if (str[i] != pattern[i])
return false;
}
return true;
}
int repeat(char* str)
{
int length = strlen(str);
int count = 0;
for (int i = 2; i <= length / 2; ++i)
{
if (length % i > 0)
continue;
count = 0;
int p = length / i;
for (int j = 1; j < p; ++j)
{... 阅读全帖 |
|
w********s
发帖数: 1570 | 20 brute force多简单，复杂度
bool isPrefix(char* pattern, char* str, int size)
{
for (int i = 0; i < size && str[i] != '\0'; ++i)
{
if (str[i] != pattern[i])
return false;
}
return true;
}
int repeat(char* str)
{
int length = strlen(str);
int count = 0;
for (int i = 2; i <= length / 2; ++i)
{
if (length % i > 0)
continue;
count = 0;
int p = length / i;
for (int j = 1; j < p; ++j)
{... 阅读全帖 |
|
w********s
发帖数: 1570 | 21 #include
#include
int max_length(std::string str)
{
int length = str.length();
if (length <= 1) return length;
int dict[26] = {0};
int i = 0;
int count = 1;
int max_length = 1;
dict[str[0] - 'a'] = 1;
for (int j = 1; j < length; ++j)
{
char c = str[j];
if (dict[c - 'a'] > 0)
{
++max_length;
}
else
{
++count;
dict[c - 'a'] = 1;
if (count > 2)
{
// erase the head char
char p = str[i];
... 阅读全帖 |
|
c**z
发帖数: 669 | 22 reverse a string
void reverse(char* str)
{
// check null
if ( str == NULL ) return;
char* end = str;
char temp;
while( *end != NULL )
end++;
end--;
while( str < end )
{
temp = *str;
*str = *end; // 这里每次都会垮掉
*end = temp;
str++;
end--;
}
} |
|
H**********5
发帖数: 2012 | 23 你的代码本身没问题，
我怀疑是你写测试时
将
char a[]=“12345”；
写成
char a*=“12345”；
导致常量字符被修改程序死掉的错误。
我刚才在VC6跑了你的代码没有问题
#include
#include
void reverse(char* str)
{
// check null
if ( str == NULL ) return;
char* end = str;
char temp;
while( *end != NULL )
end++;
end--;
while( str < end )
{
temp = *str;
*str = *end;// 这里每次都会垮掉
*end = temp;
str++;
end--;
}
}
main()
{
char a[]="12345";
reverse(a);
cout<
} |
|
g********n
发帖数: 447 | 24 网上找了一个solution是用dp的，可是这里怎么也想不明白，能指点一下吗？谢谢
partition.remove(partition.size() - 1);
为什么每次递归调用后需要把最后一个删掉呢？
谢谢
public ArrayList> partition(String s) {
ArrayList> result = new ArrayList>();
if (s == null || s.length() == 0) {
return result;
}
ArrayList partition = new ArrayList();
addPalindrome(s, 0, partition, result);
return result;
}
private void addPalindrome(String s, int start, ArrayList阅读全帖 |
|
w*******i
发帖数: 186 | 25 让start1为string里的起始点，start2为pattern里的起始点，初始值都为0.
boolean dfs(String str, int start1, char[] pattern, int start2, Map<
Character, String> map, Set visited) {
if (start1 == str.length() || start2 == pattern.length) {
return start1 == str.length() && start2 == pattern.length;
}
char ch = pattern[start2++];
if (map.containsKey(ch)) {
在map里找到对应单词
if(str能够从start1开始取到这个单词）
... 阅读全帖 |
|
w*******i
发帖数: 186 | 26 让start1为string里的起始点，start2为pattern里的起始点，初始值都为0.
boolean dfs(String str, int start1, char[] pattern, int start2, Map<
Character, String> map, Set visited) {
if (start1 == str.length() || start2 == pattern.length) {
return start1 == str.length() && start2 == pattern.length;
}
char ch = pattern[start2++];
if (map.containsKey(ch)) {
在map里找到对应单词
if(str能够从start1开始取到这个单词）
... 阅读全帖 |
|
s*****4
发帖数: 25 | 27 第四题encode, 请问要如何把code写得干净一点呢, 我的code真丑:
void encode(string &str, int n) {
for (int i = 0; i < str.size(); i++) {
char cur = str[i];
if (cur >= 'a' && cur <= 'z') {
if (cur > 'z' - n)
str[i] = 'a' + cur + n - 'z' - 1;
else
str[i] = cur + n;
} else if (cur >= 'A' && cur <= 'Z') {
if (cur > 'Z' - n)
str[i] = 'A' + cur + n - 'Z' - 1;
else
str[i] = cur + n;
... 阅读全帖 |
|
z***e
发帖数: 58 | 28
从左开始往右遍历 试图找到冒号使得分割?后面的字符串，如a?[...]:[...] 就是找到
: , 找法就是如果碰到一个 ? 就加一碰到: 就减一，这样第一个抵消?和：的也就是0
的:就是要找的冒号。然后对两个[...] 分别递归即可。随便敲了下，将就看吧。
Node createExpression(int start, int end, String str ){
if(right== left) return new Node(str[start]);
int count = 0;
Node node =new Node(str.charAt(start));
int breakIndex = 0;
for(int i = start; i <= end; ++i){
if(str.charAt(i) == '?') count++;
else if(str.charAt(i) == ':')count--;
if(count == 0) { brea... 阅读全帖 |
|
m******3
发帖数: 346 | 29 在local没问题，code如下,可能是什么原因呢？
vector findSubstring(string s, vector& words) {
int wordLen = words[0].size();
map expectedCount;
map actualCount;
for (int i=0; i
expectedCount[words[i]] = expectedCount[words[i]]++;
}
vector res;
for (int i=0; i
int left = i;
int count = 0;
for (int j=i; j<=(int)s.length()-wordLen;j=j+... 阅读全帖 |
|
B********t
发帖数: 147 | 30 Zenifits第一题
string RandomizeString(string s) {
srand(time(0));
for (int i = 1; i < s.size()-1; ++i)
swap(s[i], s[rand()%(s.size()-i-1)+i]);
return s;
}
string RandomString(string s) {
string str = s, ret("");
size_t found = str.find_first_of(" ");
while (found != string::npos) {
ret += RandomizeString(str.substr(0, found))+" ";
str = str.substr(found+1);
found = str.find_first_of(" ");
}
ret += RandomizeString(str.substr(0));
re... 阅读全帖 |
|
h*******s
发帖数: 3932 | 31 ☆─────────────────────────────────────☆
TheBigSlick (Ivan) 于 (Mon Nov 21 14:00:50 2011, 美东) 提到:
I don't have many interesting hands to share these days. I am playing boring
poker with either small gains and small loss.
But there was one hand I played serveral weeks ago that I think may be worth
discussion.
I was playing NL2/5 table, villain was a young asian in mid 20s. He sits
down with maybe $300 chips, run up to $500ish when this hand happend. I was
sitting maybe $600 chips and had him c... 阅读全帖 |
|
p*****2
发帖数: 21240 | 32
dict =
'I': true
'love': true
'you': true
dfs = (str, curr, res)->
if curr is str.length
return console.log res.join(" ")
for i in [curr...str.length]
sub = str[curr..i]
if dict[sub]
res.push sub
dfs str, i+1, res
res.pop
break_word = (str)->
dfs str, 0, []
break_word "Iloveyou" |
|
H***a
发帖数: 735 | 33 The EOF is a bit tricky. It's easy to remember that:
** always check right after you attempt to read **
There are two solutions:
1)
...
if ( infile.is_open() )
{
string str("");
getline(infile, str); //read it first!!
while ( infile.good() )
{
lines.push_back(str);
getline( infile, str ); //now get the next line!
}
infile.close();
}
...
2) Simpler way which is recommended
...
if ( infile.is_open() )
{
string str("");
while ( getline(infile, ... 阅读全帖 |
|
O*******d
发帖数: 20343 | 34 recursion和写loop一样，需要有起始值和终止条件。还要有变化值使终止条件可以达
到。 可以从简单练习做起。 例如遍历多叉树，比如把一个folder里的所有folder和文
件的名字都印出来。再简单的练习可以把一段句子反转。
void Reverse(char* begin, char* end)
{
if(end > begin)
{
char temp = *begin;
*begin = *end;
*end = temp;
Reverse(begin + 1, end - 1);
}
}
char str[] = "ABCDEFG";
Reverse(str, str + strlen(str) - 1);
如果写成循环
char* begin = str;
char* end = str+ strlen(str) - 1;
while(end > begin)
{
char temp = *begin;
*begin = *end;
*end = temp;
begin++;
end--;
}
这里的关键是一旦终... 阅读全帖 |
|
s**y
发帖数: 151 | 35 std::map和std::unordered_map都是container class容器类，里面保存了你加进去的
一对对的pair。
std::map是用一个比较function来通过Key排序／查找pair。
std::unordered_map是用一个hash function来通过Key查找pair。
所以std::map或std::unordered_map需要占据多大内存，取决于你有多少数据pair
,T>加进这个容器，这个内存大小和比较function或hash function本身无关。
hash function需要把你的每一个可能的Key转变成对应的T value，并且（1）转化快速
少用额外内存；（2）所有可能的T values尽量紧凑；（3）不同T values尽可能少出现
碰撞。
以你的6个大写字面为例子，假定每个字母是在26个字母里随机抽取。
6个大写字母字符串是Key，有26^6＝308,915,776种可能性。而T是int，按你的要求，
一个(0~2^30)的int有2^30=1,073,741,824... 阅读全帖 |
|
|
a****e
发帖数: 2064 | 37 1. What is the output of the following code?
String barb = "BARBARA";
scramble(barb);
System.out.println(barb);
\The method scramble is defined as follows;
public String scramble (String str){
if (str.length() >= 2) {
int n = str.length() / 2;
str = scramble(str.substring(n)) + str.substring(0, n);
}
return str;
}
a. BARBARA
b. ARBABAR
c. AABAR
d. ARBABARB
e. ARABARBARB
觉得这段程序不能工作，大侠们给个意见？ |
|
x********o
发帖数: 519 | 38 I remember this is a problem from Career cup
here is one approach:
#include
#include
using namespace std;
void permutation(string str, string perm){
if(str.empty()){
cout<
}
size_t n=str.size();
for(int i=0;i
string str1=str;
string perm1=perm;
perm1+=str[i];
str1.erase(i,1);
permutation(str1,perm1);
}
}
int main(){
string str("ABC");
string perm;
permutation(str,perm);
return 0;
} |
|
h******g
发帖数: 28 | 39 http://chuansong.me/n/599923051666
一、破案经过
据央视报道，在甘肃白银及内蒙古包头两地实施强奸杀人作案11起、杀死11人的犯罪嫌
疑人高承勇（男，52岁）日前在甘肃省白银市被抓获。经初步审讯，高承勇对其在1988
年5月至2002年2月间实施的犯罪事实供认不讳，白银“8·05”系列强奸杀人案由此告
破。
此系列案件作案手段残忍，社会影响恶劣，2001年8月被立为部督案件。2015年3月，甘
肃省公安厅重启侦查工作，抽调精干专家力量，紧紧围绕指纹和DNA两个方面深入侦查
。通过染色体Y-DNA检验，警方先是初步确定了犯罪嫌疑人的姓氏为高姓；后经指纹和
DNA比对，最终确定犯罪嫌疑人为高承勇。2016年8月26日，民警在白银市工业学校一小
卖部内将高承勇抓获归案。
图1 嫌犯高承勇照片
二、技术侦查
1、犯罪现场遗留的遗传物质
该犯罪嫌疑人作案多起。警方在现场提取了案犯留下的含有遗传物质的身体遗留物（精
斑、血液、唾液、皮肤、毛发等），提取其中的Y-DNA信息，输入到违法人员数据库中
，以备进一步查找。同时也提取了案发现场的指纹。
2、遗传家系的Y-DN... 阅读全帖 |
|
f****o
发帖数: 8105 | 40 【 以下文字转载自 WoldMiscNews 俱乐部 】
发信人: fuxeto (富士德), 信区: WoldMiscNews
标 题: 组图：十张图片看中国南方水灾
发信站: BBS 未名空间站 (Mon Jul 11 07:35:11 2016, 美东)
中国大陆南方，接连多场暴雨引发洪灾。图为2016年7月7日，湖北武汉，道路淹水，民
众在门口堆上沙包并用水桶清理积水。 (Wang He/Getty Images)
6月下旬以来，中国大陆南方接连多场暴雨引发洪灾，波及长江、珠江西江流域，有近
百条河流超出警戒水位，波及七八个省市，除了民众生计受到严重影响外，也造成了难
以估计的经济损失。根据气象预报，暴雨仍在持续，大洪水的风险也随之增加。
中国大陆南方，接连多场暴雨引发洪灾。图为2016年7月2日，湖北武汉，一辆汽车在淹
水的道路前进。摄(STR/AFP/Getty Images)
中国大陆南方，接连多场暴雨引发洪灾。图为2016年7月2日，湖北武汉，一辆汽车在淹
水的道路前进。摄(STR/AFP/Getty Images)
中国大陆南方，接连多场暴雨引发洪灾。图为2016年... 阅读全帖 |
|
i****x
发帖数: 17565 | 41 不知道你跑过赛道没有，上赛道没你想得那么容易，大多数赛道都要求对车有一些改装
，比如roll bar和赛车座椅。即使是很纯正跑车不改也是不让上的。
如果你真的要买跑车严肃地玩autocross或者赛道，那就简单了。s2000，miata，fr-s
，350z，rx8。至于slk，z4，都花很多心思在luxury上，用来跑赛道性价比太低了，而
像TT这样上赛道更是搞笑，完全没有性价比可言了。你应该去auto fans俱乐部问这个
问题，这个版主要是讨论拉人买菜车的。
附上我这里某次autocross的参赛车款列表，你看看都是什么车就有数了。
2 5 XDSP 185 Steven Rankins 99 Spec OPS Subaru 54.728 5
.381 5.381
3 10 XBSP 43 Kevin Allen 2002 Subaru WRX 55.370 0.642
6.023
4 8 XDSP 85 Jon Krolewicz 99 Spec OPS... 阅读全帖 |
|
i****x
发帖数: 17565 | 42 虽然说civic是跑车太夸张，但作为sports hatch，civic是非常强的。你看看下面这个
按成绩排序的autocross车款列表就知道了
Raw
Pos. Pos. Class # Driver Car Model Raw
Time Diff. From
1st
1 9 XF125 50 Keith Vail 2005 Intrepid Explorer 49.347 0
.000 0.000
2 5 XDSP 185 Steven Rankins 99 Spec OPS Subaru 54.728 5
.381 5.381
3 10 XBSP 43 Kevin Allen 2002 Subaru WRX 55.370 0.642
6.023
4 8 XDSP 85 Jon Krolewicz 99 Spec OPS Subaru 55.417 ... 阅读全帖 |
|
a******h
发帖数: 19 | 43 // only needs gcd(strLen, k) times circular swap
// this function supports right rotation only
public static String rotateStr(String str, int k) {
if (str == null)
return null;
if (k == 0 || str.length() == k)
return str;
if (k < 0)
throw new InvalidParameterException();
char [] arr = str.toCharArray();
int gcd = findGCD(str.length(), k);
for (int i = 0; i < gcd; i++) {
|
|
c*********n
发帖数: 1057 | 44 多谢指教，用你的思想写了下code,各位看看对不对：
//L[i][j] = L[i+1][j-1] && s[i]==s[j]
public static int findNumberOfPalindrom(String str){
boolean[][] L = new boolean[str.length()][str.length()];
int count=0;
//Init
int i;
for(i=0;i
L[i][i]=true;
}
//From substring with length 3 to max length
for(int k = 2;k
for(i=0;i
L[i][i+k]=L[i+1][i |
|
a****n
发帖数: 1887 | 45 5.
memset (str,0,sizeof(str));
memset (str,1,sizeof(str));
memset (str,0xff00,sizeof(str));
有没有问题？
这三个语句初始化后的内存是什么样子的 |
|
P********l
发帖数: 452 | 46 How about this version using Dynamic Programming?
The basic idea is fill in a table for a matching path. If the last pair
matches, the whole string will match.
mtch is the array, which is of (string length + 1)*(pattern length + 1).
mtch[0][*] and mtch[*][0] is padded with false.
Then the function is something like:
mtch[i][j] =
1. if pattern char='.', mtch[i][j]=mtch[i-1][j-1]
2. if pattern char='*', mtch[i][j]=mtch[i-1][j-1] || mtch[i][j]=mtch[i-1][
j]
3. if pattern char=string char, mtc... 阅读全帖 |
|
|
P********l
发帖数: 452 | 48 Fixed the issue ihasleetcode mentioned. Thanks.
Added more test cases like:
string = "ho"
pattern = "**ho", "ho**"
string = "a", pattern = "aa"
string = "aa", pattern = "a"
Code:
/**
* check if patt matches the string str. Same as {@link match} but
* one-dimension array is used.
*
* @param str
* the string to match
* @param patt
* the pattern matching str. '*' is for 0 or more characters
and
* '.' is for exactly one cha... 阅读全帖 |
|
s*********3
发帖数: 389 | 49 The wrong part is actually
else return 1 + f(str.substring(1, n));
It should be:
else return Math.min(1 + f(str.substring(1, n)), 1 + f(str.substring(0, n-1)
));
Also, it needs to check if str is null as follows:
if (null == str || str.length() <= 1) return 0; |
|
