Skip to content

Commit c851bad

Browse files
varunu28varunu28
committed
Added 2 solutions & modified 2 solutions
1 parent 33ec853 commit c851bad

File tree

4 files changed

+122
-51
lines changed

4 files changed

+122
-51
lines changed

‎Hard/N-Queens.java

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
class Solution {
2+
public List<List<String>> solveNQueens(int n) {
3+
List<List<String>> ans = new ArrayList <>();
4+
helper(n, 0, new ArrayList<>(), ans);
5+
return ans;
6+
}
7+
8+
private void helper(int n, int row, List<Integer> selections, List<List<String>> ans) {
9+
if (row == n) {
10+
ans.add(convertToString(selections, n));
11+
}
12+
else {
13+
for (int i = 0; i < n; i++) {
14+
selections.add(i);
15+
if (isValid(selections)) {
16+
helper(n, row + 1, selections, ans);
17+
}
18+
selections.remove(selections.size() - 1);
19+
}
20+
}
21+
}
22+
23+
private List <String> convertToString(List <Integer> selections, int n) {
24+
List<String> ret = new ArrayList<>();
25+
for (int i = 0; i < selections.size(); i++) {
26+
StringBuilder sb = new StringBuilder();
27+
for (int j = 0; j < n; j++) {
28+
if (j == selections.get(i)) {
29+
sb.append("Q");
30+
}
31+
else {
32+
sb.append(".");
33+
}
34+
}
35+
ret.add(sb.toString());
36+
}
37+
return ret;
38+
}
39+
40+
private boolean isValid(List <Integer> selections) {
41+
int row = selections.size() - 1;
42+
for (int i = 0; i < row; i++) {
43+
int diff = Math.abs(selections.get(i) - selections.get(row));
44+
if (diff == 0 || diff == row - i) {
45+
return false;
46+
}
47+
}
48+
return true;
49+
}
50+
}

‎Hard/Word Break II.java

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
class Solution {
2+
Map<Integer, List<String>> map = new HashMap<>();
3+
public List<String> wordBreak(String s, List <String> wordDict) {
4+
Set<String> set = new HashSet<>(wordDict);
5+
return helper(s, set, 0);
6+
}
7+
8+
private List<String> helper(String s, Set<String> set, int start) {
9+
if (map.containsKey(start)) {
10+
return map.get(start);
11+
}
12+
13+
List<String> ans = new ArrayList <>();
14+
if (start == s.length()) {
15+
ans.add("");
16+
}
17+
for (int i = start + 1; i <= s.length(); i++) {
18+
if (set.contains(s.substring(start, i))) {
19+
List<String> list = helper(s, set, i);
20+
for (String word : list) {
21+
ans.add(s.substring(start, i) + (word.equals("") ? "" : " ") + word);
22+
}
23+
}
24+
}
25+
26+
map.put(start, ans);
27+
return ans;
28+
}
29+
}

‎Medium/Permutations II.java

Lines changed: 22 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -1,32 +1,28 @@
11
class Solution {
2-
public static List<List<Integer>> permuteUnique(int[] nums) {
3-
List<List<Integer>> ans = new ArrayList<>();
4-
Arrays.sort(nums);
5-
permuteHelper(nums, new ArrayList<>(), ans, new boolean[nums.length]);
6-
return new ArrayList<>(ans);
2+
public List<List<Integer>> permuteUnique(int[] nums) {
3+
Set<List<Integer>> ans = new HashSet <>();
4+
Map <Integer, Integer> map = new HashMap <>();
5+
for (int num : nums) {
6+
map.put(num, map.getOrDefault(num, 0) + 1);
77
}
8+
permuteHelper(nums, nums.length, ans, map, new ArrayList<>());
9+
return new ArrayList <>(ans);
10+
}
811

9-
private static void permuteHelper(int[] nums, List<Integer> list, List<List<Integer>> ans, boolean[] used) {
10-
if (list.size() == nums.length) {
11-
ans.add(new ArrayList<>(list));
12-
}
13-
else {
14-
for (int i=0; i<nums.length; i++) {
15-
// Choose
16-
if (used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1])) {
17-
continue;
18-
}
19-
20-
used[i] = true;
21-
list.add(nums[i]);
22-
23-
// Explore
24-
permuteHelper(nums, list, ans, used);
12+
private void permuteHelper(int[] nums, int length, Set<List<Integer>> ans, Map<Integer, Integer> used, ArrayList<Integer> curr) {
13+
if (curr.size() == length) {
14+
ans.add(new ArrayList <>(curr));
15+
return;
16+
}
2517

26-
// Un-choose
27-
used[i] = false;
28-
list.remove(list.size()-1);
29-
}
30-
}
18+
for (int i = 0; i < length; i++) {
19+
if (used.get(nums[i]) != 0) {
20+
used.put(nums[i], used.get(nums[i]) - 1);
21+
curr.add(nums[i]);
22+
permuteHelper(nums, length, ans, used, curr);
23+
used.put(nums[i], used.get(nums[i]) + 1);
24+
curr.remove(curr.size() - 1);
25+
}
3126
}
27+
}
3228
}

‎Medium/Permutations.java

Lines changed: 21 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -1,30 +1,26 @@
11
class Solution {
2-
public List<List<Integer>> ans = new ArrayList<>();
3-
4-
public List<List<Integer>> permute(int[] nums) {
5-
List<Integer> list = new ArrayList<>();
6-
permuteHelper(nums, list, 0);
7-
return ans;
8-
}
9-
10-
private void permuteHelper(int[] nums, List<Integer> list, int idx) {
11-
if (list.size() == nums.length) {
12-
ans.add(new ArrayList<>(list));
13-
}
14-
else {
15-
for (int i=0; i<nums.length; i++) {
16-
// Choose
17-
if (list.contains(nums[i])) {
18-
continue;
19-
}
20-
list.add(nums[i]);
2+
public List<List<Integer>> permute(int[] nums) {
3+
List<List<Integer>> ans = new ArrayList <>();
4+
Set<Integer> used = new HashSet <>();
5+
permuteHelper(nums, nums.length, ans, used, new ArrayList<>());
6+
return ans;
7+
}
218

22-
// Explore
23-
permuteHelper(nums, list, i+1);
9+
private void permuteHelper(int[] nums, int length, List<List<Integer>> ans,
10+
Set<Integer> used, ArrayList<Integer> curr) {
11+
if (curr.size() == length) {
12+
ans.add(new ArrayList <>(curr));
13+
return;
14+
}
2415

25-
// Un-choose
26-
list.remove(list.size()-1);
27-
}
28-
}
16+
for (int i = 0; i < length; i++) {
17+
if (!used.contains(nums[i])) {
18+
used.add(nums[i]);
19+
curr.add(nums[i]);
20+
permuteHelper(nums, length, ans, used, curr);
21+
used.remove(nums[i]);
22+
curr.remove(curr.size() - 1);
23+
}
2924
}
25+
}
3026
}

0 commit comments

Comments
 (0)