motorola citrus上可以装alf的测光表么？# PhotoGear - 摄影器材
J*9
1 楼
Problem at
http://discuss.leetcode.com/questions/765/word-break
This does not seem to be a DP problem, just do it in a straightforward way.
Here's my implementation in C. Any issue?
Thanks.
//===========================================================
#include
#include
#include
#include
#include
/**
* Given a string s and a dictionary of words dict, determine if s can be
segmented into a space-separated sequence of one or more
* dictionary words.
*
* For example, given
* s = "leetcode",
* dict = ["leet", "code"].
*
* Return true because "leetcode" can be segmented as "leet code".
*/
void stringGetSubstr(const char *word, char *substr, int start, int end)
{
if (!word || !substr)
return;
char *d = substr;
for(int i=start; i
*d = '\0';
printf("%s(): substr=%s\n", __FUNCTION__, substr);
}
bool stringDictContains(const char *substr, const char *dict[])
{
if (!substr)
return true;
if (!dict)
return false;
int i=0;
while(dict[i])
{
if (!strcmp(dict[i], substr))
return true;
i++;
}
return false;
}
bool stringWordBreakable(const char *word, const char *dict[])
{
if (!word || !dict)
return false;
int len = strlen(word);
char substr[len+1];
char substr2[len+1];
if (stringDictContains(word, dict))
return true;
for(int i=1; i
stringGetSubstr(word, substr, 0, i);
if (stringDictContains(substr, dict))
{
stringGetSubstr(word, substr2, i, len);
if (stringDictContains(substr2, dict))
{
printf("Got it: %s %s\n", substr, substr2);
return true;
}
}
}
return false;
}
int main (int argc, char *argv[])
{
const char *word = "leetcode";
const char *dict[] = { "leet", "code", NULL};
if (stringWordBreakable(word, dict))
printf("breakable:YES\n");
else
printf("breakable:NO\n");
const char *word2 = "leetscode";
if (stringWordBreakable(word2, dict))
printf("breakable:YES\n");
else
printf("breakable:NO\n");
return 0;
}
/**
* stringGetSubstr(): substr=l
* stringGetSubstr(): substr=le
* stringGetSubstr(): substr=lee
* stringGetSubstr(): substr=leet
* stringGetSubstr(): substr=code
* Got it: leet code
* breakable:YES
* stringGetSubstr(): substr=l
* stringGetSubstr(): substr=le
* stringGetSubstr(): substr=lee
* stringGetSubstr(): substr=leet
* stringGetSubstr(): substr=scode
* stringGetSubstr(): substr=leets
* stringGetSubstr(): substr=leetsc
* stringGetSubstr(): substr=leetsco
* stringGetSubstr(): substr=leetscod
* breakable:NO
*
*/
http://discuss.leetcode.com/questions/765/word-break
This does not seem to be a DP problem, just do it in a straightforward way.
Here's my implementation in C. Any issue?
Thanks.
//===========================================================
#include
#include
#include
#include
#include
/**
* Given a string s and a dictionary of words dict, determine if s can be
segmented into a space-separated sequence of one or more
* dictionary words.
*
* For example, given
* s = "leetcode",
* dict = ["leet", "code"].
*
* Return true because "leetcode" can be segmented as "leet code".
*/
void stringGetSubstr(const char *word, char *substr, int start, int end)
{
if (!word || !substr)
return;
char *d = substr;
for(int i=start; i
*d = '\0';
printf("%s(): substr=%s\n", __FUNCTION__, substr);
}
bool stringDictContains(const char *substr, const char *dict[])
{
if (!substr)
return true;
if (!dict)
return false;
int i=0;
while(dict[i])
{
if (!strcmp(dict[i], substr))
return true;
i++;
}
return false;
}
bool stringWordBreakable(const char *word, const char *dict[])
{
if (!word || !dict)
return false;
int len = strlen(word);
char substr[len+1];
char substr2[len+1];
if (stringDictContains(word, dict))
return true;
for(int i=1; i
stringGetSubstr(word, substr, 0, i);
if (stringDictContains(substr, dict))
{
stringGetSubstr(word, substr2, i, len);
if (stringDictContains(substr2, dict))
{
printf("Got it: %s %s\n", substr, substr2);
return true;
}
}
}
return false;
}
int main (int argc, char *argv[])
{
const char *word = "leetcode";
const char *dict[] = { "leet", "code", NULL};
if (stringWordBreakable(word, dict))
printf("breakable:YES\n");
else
printf("breakable:NO\n");
const char *word2 = "leetscode";
if (stringWordBreakable(word2, dict))
printf("breakable:YES\n");
else
printf("breakable:NO\n");
return 0;
}
/**
* stringGetSubstr(): substr=l
* stringGetSubstr(): substr=le
* stringGetSubstr(): substr=lee
* stringGetSubstr(): substr=leet
* stringGetSubstr(): substr=code
* Got it: leet code
* breakable:YES
* stringGetSubstr(): substr=l
* stringGetSubstr(): substr=le
* stringGetSubstr(): substr=lee
* stringGetSubstr(): substr=leet
* stringGetSubstr(): substr=scode
* stringGetSubstr(): substr=leets
* stringGetSubstr(): substr=leetsc
* stringGetSubstr(): substr=leetsco
* stringGetSubstr(): substr=leetscod
* breakable:NO
*
*/
