三年经验
第一轮：
/*
Write a function
Input => sentence, {"a", "the", "what", "is", "java".... "zoo"}
Output => the sentence but split by space into constituent words
Example:
Input => "whatisjava", <same dictionary as above>
Output-> "what is java"
*/
import java.util.*;
public class Solution {
public static String split(String s, Set<String> dict) {
return breakWords(s, 0, dict, new HashMap<>());
}
// trie
// index -> Integer, 0 ~
// whatisjava
// prefix: what
// suffix: isjava
// whatwhatjavajava
// abcabcabc
// abc
// abcabc
// abcabcabc
// 012345678
//
// abc
// dp[k] substring 0: k - 1
//
private static String breakWords(String s, int beg, Set<String> dict, Map<Integer, String> memo) {
if (s == null || beg == s.length()) {
return null;
}
if (memo.containsKey(beg)) {
return memo.get(beg);
}
for (int i = beg + 1; i <= s.length(); i++) {
String prefix = s.substring(beg, i);
if (!dict.contains(prefix)) {
continue;
}
if (i == s.length()) {
memo.put(beg, prefix);
return prefix;
}
String segSuffix = breakWords(s, i, dict, memo);
if (segSuffix != null) {
String res = prefix + " " + segSuffix;
memo.put(beg, res);
return res;
}
}
memo.put(beg, null);
return null;
}
public static void main(String[] args) {
System.out.println(split("whatisjava",
new HashSet<>(Arrays.asList("a", "whati", "sjava", "the", "what", "is", "java", "zoo"))));
// System.out.println("done");
}
}
第二轮
https://leetcode.com/problems/diagonal-traverse/discuss/97711/Java-15-lines-without-using-boolean 变种
第二题类似 Reconstruct Itinerary，但是要求 min cost ，给了每个city之间的cost, dfs 解决
public static void diagonal(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int r, c;
for (int i = 0; i < n; i++) {
r = 0;
c = i;
while (c >= 0 && r < m) {
System.out.print(matrix[r][c] + " ");
r++;
c--;
}
System.out.println();
}
for (int i = 1; i < m; i++) {
r = i;
c = n - 1;
while (c >= 0 && r < m) {
System.out.print(matrix[r][c] + " ");
r++;
c--;
}
System.out.println();
}
}
第三轮
Project Deep Dive 和一堆BQ，没考题目
第四轮
Design Instagram