Word Break
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".
-----------------------------------------------------------------------
Just DP
dp[i] has the boolean value that means if string[i : n] can be partitioned according to our dictionary. Hence dp[len] represents the empty string and dp[0] is the answer we are looking for.
For each iteration in the inner for loop, we add a new cut at index j to string[i : n], in whcih string[i : j] has never checked before but string[j + 1 : n](result is in dp[j + 1]) has been known since the previous iteration in outer loop.
class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
int len = s.length();
vector<bool> dp(len + 1,false);
dp[len] = true;
for (int i = len - 1; i >= 0; i--) {
for (int j = i; j < len; j++) {
string str = s.substr(i,j - i + 1);
if (dict.find(str) != dict.end() && dp[j + 1]) {
dp[i] = true;
break;
}
}
}
return dp[0];
}
};
Java, memoization. Updated on Jun-25th-2018
class Solution {
public boolean wordBreak(String s, List wordDict) {
Map m = new HashMap<>();
return dfs(s, new HashSet(wordDict), m);
}
private boolean dfs(String s, Set dic, Map m) {
if (s.length() == 0) return true;
for (int i = 0; i < s.length(); i++) {
String sub = s.substring(0, i + 1);
String nextSub = s.substring(i + 1);
if (!dic.contains(sub)) {
continue;
}
boolean next;
if (m.containsKey(nextSub)) {
next = m.get(nextSub);
}else {
next = dfs(s.substring(i + 1), dic, m);
}
if (next) return true;
}
m.put(s, false);
return false;
}
}
ToDo: 有意思的bfs，把每个单词当作是node，queue里可以存index
https://leetcode.com/problems/word-break/discuss/43797/A-solution-using-BFS
Word Break II
Given a string
s and a dictionary of words
dict, add spaces in
s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s =
"catsanddog",
dict =
["cat", "cats", "and", "sand", "dog"].
A solution is
["cats and dog", "cat sand dog"].
-----------------------------------------------
Based on Word Break, add one more DP to store all possible partition at current index
因为LC加了新的test case，以下代码得加一段word break I的代码，来先检测s是否能被分解
class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string> &dict) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int len = s.length();
vector<bool> dp(len + 1,false);
vector<vector<string> > dp2(len + 1,vector<string>());
dp2[len].push_back("");
dp[len] = true;
for (int i = len - 1; i >= 0; i--) {
for (int j = i; j < len; j++) {
string str = s.substr(i,j - i + 1);
if (dict.find(str) != dict.end() && dp[j + 1]) {
dp[i] = true;
for (int index = 0; index < dp2[j + 1].size(); index++) {
string empty = "";
if (j + 1 != len) empty = " ";
string n = str + empty + dp2[j + 1][index];
dp2[i].push_back(n);
}
}
}
}
return dp2[0];
}
};
dfs,减枝之后也能过OJ
class Solution {
public:
void dfs(vector<string> &rt, string s, int index,string cur, unordered_set<string>& wordDict) {
if (index == s.length()) {
rt.push_back(cur);
return;
}
bool notFound = true;
for (int i = s.size() - 1; i >= index; --i) {
if (wordDict.find(s.substr(i)) != wordDict.end()) {
notFound = false;
break;
}
}
if (notFound) { return ; }
for (int i = index; i < s.length(); i++) {
string sub = s.substr(index,i - index + 1);
if (wordDict.find(sub) != wordDict.end()) {
string t = cur;
if (t.length() == 0) {
t = sub;
}else {
t += " " + sub;
}
dfs(rt,s,i + 1,t,wordDict);
}
}
}
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
vector<string> rt;
dfs(rt,s,0,"",wordDict);
return rt;
}
};
Java，在Word Break I的基础上进行修改的dfs. Updated on Jun-26th-2018
class Solution {
public List wordBreak(String s, List wordDict) {
return dfs(s, new HashSet(wordDict), new HashMap>());
}
private List dfs(String s, Set dic, Map> m) {
if (s.length() == 0) return new ArrayList<>();
List rt = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
String sub = s.substring(0, i + 1);
String nextSub = s.substring(i + 1);
if (!dic.contains(sub)) {
continue;
}
List next;
if (m.containsKey(nextSub)) {
next = m.get(nextSub);
}else {
next = dfs(s.substring(i + 1), dic, m);
}
for (String can : next) {
rt.add(sub + " " + can);
}
if (i == s.length() - 1) {
rt.add(sub);
}
}
m.put(s, rt);
return rt;
}
}
Todo: 写一个iterate版本的
Linked List Cycle
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
--------------------------------------------------------------
two pointers, one traverses twice as fast as the other
return true if they meet
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if (head == NULL) return false;
ListNode *slow = head, *fast = head->next;
bool flag = false;
while (fast != NULL) {
if (fast == slow) {
flag = true;
break;
}
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
return flag;
}
};
Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return
null.
Follow up:
Can you solve it without using extra space?
-----------------------------------------------------------------
Floyd's cycle-finding algorithm
Note: as opposed to Linked List Cycle
1) fast is initialized to head, not head->next
2) if (fast == slow) is executed after pointers've been moved
Update Dec-30th-2014
假设 x 为起跑线到loop的起点的距离，y为该起点到两个指针相遇点的距离，z为该点到起点的距离，则loop的长度 L = y + z
m 为慢指针在相遇时跑过的距离： m = x + y
n 为快指针在相遇时跑过的距离： n = x + y + k * L, k > 0
已知 2m = n
2(x + y) = x + y + k * L
x = k * L - y
x = (k - 1) * L + z
证毕
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (head == NULL) return false;
ListNode *slow = head, *fast = head;
bool flag = false;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
if (fast == slow) {
flag = true;
break;
}
}
if (!flag) return NULL;
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
};
