Problem Statement:
Given an integer array nums, find a subarray that has the largest product, and return the product.
The test cases are generated so that the answer will fit in a 32-bit integer.
Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Constraints
1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10- The product of any subarray of
numsis guaranteed to fit in a 32-bit integer.
Approach:
- Use
recursion to try breaking the string sinto valid dictionary words. - At each step,
check all prefixesof the remaining string.- If the
prefix is in wordDict, recursively check the rest of the string.
- If the
- Use a
memoization map dpto store results for substrings toavoid repeated works. - If any split leads to the entire string being segmented into
valid words, return true; otherwise return false.
Time & Space Complexity:
Time Complexity: O(n2)
Space Complexity: O(n)
Dry Run
Input: s = "leetcode", wordDict = ["leet", "code"]
Start: wordBreak("leetcode", ["leet","code"])
dp = {}
Call fn("leetcode"):
remS = "leetcode", res = false
i = 0 → substr = "l" → not in dict
i = 1 → substr = "le" → not in dict
i = 2 → substr = "lee" → not in dict
i = 3 → substr = "leet" → in dict → call fn("code")
Call fn("code"):
remS = "code", res = false
i = 0 → substr = "c" → not in dict
i = 1 → substr = "co" → not in dict
i = 2 → substr = "cod" → not in dict
i = 3 → substr = "code" → in dict → call fn("")
Call fn(""):
remS = "" → base case → return true
fn("code"): fn("") returned true → res = true
dp["code"] = true
return true
fn("leetcode"): fn("code") returned true → res = true
dp["leetcode"] = true
return true
Final dp: { "code": true, "leetcode": true }
Return: true
Output: true
var wordBreak = function(s, wordDict) {
let dp = {};
let fn = (remS) => {
if(remS === "") return true;
if(remS in dp) return dp[remS];
let res = false;
for(let i=0; i< remS.length; i++){
let substr = remS.substring(0, i+1);
if(wordDict.includes(substr) && fn(remS.substring(i + 1))) {
res = true;
}
}
return dp[remS] = res;
}
return fn(s);
};
def wordBreak(s, wordDict):
dp = {}
def fn(remS):
if remS == "":
return True
if remS in dp:
return dp[remS]
res = False
for i in range(len(remS)):
substr = remS[:i+1]
if substr in wordDict and fn(remS[i+1:]):
res = True
break
dp[remS] = res
return res
return fn(s)
import java.util.*;
public class Solution {
public boolean wordBreak(String s, List wordDict) {
Map dp = new HashMap<>();
return fn(s, wordDict, dp);
}
private boolean fn(String remS, List wordDict, Map dp) {
if (remS.equals("")) return true;
if (dp.containsKey(remS)) return dp.get(remS);
boolean res = false;
for (int i = 0; i < remS.length(); i++) {
String substr = remS.substring(0, i + 1);
if (wordDict.contains(substr) && fn(remS.substring(i + 1), wordDict, dp)) {
res = true;
break;
}
}
dp.put(remS, res);
return res;
}
}
#include <bits/stdc++.h>
using namespace std;
bool fn(const string &remS, const vector &wordDict, unordered_map &dp) {
if (remS == "") return true;
if (dp.find(remS) != dp.end()) return dp[remS];
bool res = false;
for (size_t i = 0; i < remS.size(); ++i) {
string substr = remS.substr(0, i+1);
if (find(wordDict.begin(), wordDict.end(), substr) != wordDict.end() &&
fn(remS.substr(i+1), wordDict, dp)) {
res = true;
break;
}
}
dp[remS] = res;
return res;
}
bool wordBreak(string s, vector& wordDict) {
unordered_map dp;
return fn(s, wordDict, dp);
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define HASH_SIZE 10007
typedef struct Entry {
char *key;
int val; // 0 => false, 1 => true
struct Entry *next;
} Entry;
Entry* table[HASH_SIZE];
unsigned long djb2(const char *str) {
unsigned long hash = 5381;
int c;
while ((c = *str++))
hash = ((hash << 5) + hash) + c;
return hash;
}
void dp_set(const char *key, int val) {
unsigned long h = djb2(key) % HASH_SIZE;
Entry *e = table[h];
while (e) {
if (strcmp(e->key, key) == 0) {
e->val = val;
return;
}
e = e->next;
}
Entry *ne = (Entry*)malloc(sizeof(Entry));
ne->key = strdup(key);
ne->val = val;
ne->next = table[h];
table[h] = ne;
}
int dp_get(const char *key, int *out) {
unsigned long h = djb2(key) % HASH_SIZE;
Entry *e = table[h];
while (e) {
if (strcmp(e->key, key) == 0) {
*out = e->val;
return 1;
}
e = e->next;
}
return 0;
}
bool fn(const char *remS, char **wordDict, int wordCount) {
if (remS[0] == '\0') return true;
int cached;
if (dp_get(remS, &cached)) return cached ? true : false;
bool res = false;
size_t len = strlen(remS);
for (size_t i = 0; i < len; ++i) {
size_t prefixLen = i + 1;
char *substr = (char*)malloc(prefixLen + 1);
strncpy(substr, remS, prefixLen);
substr[prefixLen] = '\0';
bool included = false;
for (int w = 0; w < wordCount; ++w) {
if (strcmp(wordDict[w], substr) == 0) {
included = true;
break;
}
}
if (included) {
const char *nextRem = remS + prefixLen;
if (fn(nextRem, wordDict, wordCount)) {
res = true;
free(substr);
break;
}
}
free(substr);
}
dp_set(remS, res ? 1 : 0);
return res;
}
using System;
using System.Collections.Generic;
public class Solution {
public bool WordBreak(string s, IList wordDict) {
var dp = new Dictionary();
return Fn(s, wordDict, dp);
}
private bool Fn(string remS, IList wordDict, Dictionary dp) {
if (remS == "") return true;
if (dp.ContainsKey(remS)) return dp[remS];
bool res = false;
for (int i = 0; i < remS.Length; i++) {
string substr = remS.Substring(0, i + 1);
if (wordDict.Contains(substr) && Fn(remS.Substring(i + 1), wordDict, dp)) {
res = true;
break;
}
}
dp[remS] = res;
return res;
}
}
