Leetcode(C++)
題目 : https://leetcode.com/problems/word-break/ 。
想法 :
陣列代表的狀態是這一格能不能成功有字串走過來 : 也就是這個字典裡有沒有這個子字串。
接著枚舉所有字串並更新陣列的狀態。
時間複雜度 : O(s.len * wordDict.size() * wordDict[i].len)
程式碼 :
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int l=wordDict.size(), len_s=s.size(), dp[310]={0}, now=0;
dp[0]=1;
while(dp[now] == 1 && now < len_s){
for(int i=0 ; i<l ; i++){
if(wordDict[i].size() <= len_s-now){
string str=s.substr(now,wordDict[i].size());
//cout << str << " " << wordDict[i] << endl;
if(str == wordDict[i]){
dp[now+wordDict[i].size()]=1;
}
}
}
now++;
while(dp[now] != 1 && now < len_s){
now++;
}
}
/*for(int i=0 ; i<=len_s ; i++){
cout << dp[i];
}*/
return dp[len_s];
}
};
題目 : https://leetcode.com/problems/richest-customer-wealth/ 。 想法 : 語法。 時間複雜度 : O(n*m)。 程式碼 : (JAVA)
Feb 5, 2022題目 : https://leetcode.com/problems/coin-change-2/ 。 想法 : 無窮背包問題。 時間複雜度 : O(n*m)。 程式碼 : (JAVA)
Feb 5, 2022題目 : https://leetcode.com/problems/integer-break/ 。 想法 : 規律就在2跟3身上(?),把一個數字分解成2跟3的總和就好。 時間複雜度 : O(1)。 程式碼 : (JAVA)
Feb 5, 2022題目 : https://leetcode.com/problems/longest-common-subsequence/ 。 想法 : LCS。 if(str[i] == str[j]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
Feb 5, 2022or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up