dgbfs
BAN USERsort the person by the height
if the count is not zero, swap the person on the right who is higher until the count become zero
time: O(n^2)
example 1
235461
020004
sort
123456
402000
swap 1
234516
020000
swap 3
245316
000000
example 2
3 1 2 4
0 2 1 0
sort
1 2 3 4
2 1 0 0
swap 1
2 3 1 4
1 0 0 0
swap 2
3 2 1 4
0 0 0 0
this can be done with the prev pointer without using the stack (even one stack)
it call fillRight and fillLeft alternatively in which there are two pointers
p iterates along the current level with the prev pointer and r iterates along the next level with the next
fill the left and right child accordingly and return the last node of the next level
for example
level 1: fill node 1 and return the last node 3
leve 2: fill node 3 and then 2 and return the last node 7
level 3: fill node 7 and return the last node 8
leve 4: fille node 8 and return null
void fillRight(ListNode node)
{
ListNode p = node; // p iterate along the current level using the prev pointer
ListNode prev = null;
ListNode r = p.next; // r iterate along the next level using the next pointer
if (r != null)
r.prev = null;
while (p != null) // fill the right child first
prev = p.prev;
p.next = r // next for right
if (r != null)
r = r.next;
p.prev = r; // prev for left
if (r != null)
r = r.next;
p = prev;
}
return r;
}
void fillLeft(ListNode node)
{
ListNode p = node;
ListNode prev = null;
ListNode r = p.next;
if (r != null)
r.prev = null;
while (p != null) { // fill the left child first
prev = p.prev;
p.prev = r; // prev for left
if (r != null)
r = r.next;
p.next = r; // next for right
if (r != null)
r = r.next;
p = prev;
}
return r;
}
void convert(ListNode head)
{
ListNODE p = head;
boolean right = true;
while (p != null) {
ListNode q;
if(right) {
q = fillRight(p);
} else {
q = fillLeft(p);
}
right = !right;
p = q;
}
}
Solution
choose the first station as the starting point
maintain the total capacity and total distance from the starting station to the current station,
if total capacity is less than the total distance, no gas station between the starting station and the current one can be the starting station, choose the next station as starting point, add the total capacity and distance to the total capacity and distance and from 0 to start (avoiding recalculation)
when the pointer reach the last element, verify if the total capacity is less than total distance
ideone.com/Xx4S2c
public int getStartingStation(int[] cost, int[] dist)
{
int start = 0;
int capacityFromStart = 0; // total capacity from the starting station
int distFromStart = 0; // total distance from the starting stations
int capacityToStart = 0; // total capacity from 0 to the starting station (exclusively)
int distToStart = 0; // total distance from 0 to the starting station (exclusively)
for(int i = 0; i < cost.length; i++) {
capacityFromStart += cost[i];
distFromStart += dist[i];
if(capacityFromStart < distFromStart) {
capacityToStart += capacityFromStart;
distToStart += distFromStart;
start = i + 1;
capacityFromStart = 0;
distFromStart = 0;
}
}
if(capacityFromStart + capacityToStart < distFromStart + distToStart) throw new NoSuchElementException();
return start;
}
use parent array p, where p[i] store the parent of (i + 1)
1
/ \
2 4
\
3
0 1 2 3
0 1 4 1
perform the preorder traverse
set the point for itself
also traverse the parent array and set point for the ancestors
recursively fill the ancestor for its children
Worse Case Time: O(n^2) if the trace is completely unbalanced
O(nlgn) if the tree is balanced
ideone.com/WUijFA
public void fill(TreeNode root, int[][] a)
{
int[] p = new int[a.length];
fill(root, a, p);
}
private void fill(TreeNode root, int[][] a, int[] p)
{
if(root == null) return;
a[root.val - 1][root.val - 1] = 1;
for(int parent = p[root.val - 1]; parent > 0; parent = p[parent - 1])
a[parent - 1][root.val - 1] = 1;
if(root.left != null) {
p[root.left.val - 1] = root.val;
fill(root.left, a, p);
}
if(root.right != null) {
p[root.right.val - 1] = root.val;
fill(root.right, a, p);
}
}
Algorithm
similar as the linear majority voting algorithm, we maintains two numbers having top two votes
if it's the number having the top votes, increment the top votes by 1
if it's the number having the second top votes, increment the second votes by 1 and swap it with the top votes number if it has more votes
if the number having the top votes is not defined, make the number top votes with vote 1
if the number having the second top votes is not defined, make the number second top votes with vote 1
otherwise, decrement the votes of top two votes
when the votes become zero, the number of the top or the second top are undefined
Time: O(n)
Space: O(1)
ideone.com/8yNNIW
public void find(int[] a)
{
int first = Integer.MIN_VALUE; // the number with the top votes
int firstVote = 0; // the top votes
int second = Integer.MIN_VALUE; // the number with the second top votes
int secondVote = 0; // the second top votes
for(int i: a) {
if(firstVote > 0 && i == first) {
firstVote++;
} else if(secondVote > 0 && i == second) {
secondVote++;
if(secondVote > firstVote) {
int t = first;
first = second;
second = t;
t = firstVote;
firstVote = secondVote;
secondVote = t;
}
} else if(firstVote == 0) {
first = i;
firstVote++;
} else if(secondVote == 0) {
second = i;
secondVote++;
} else {
firstVote--;
secondVote--;
}
}
// confirm if the number with top 2 votes occurs more than 3/n times
int firstCount = 0;
int secondCount = 0;
//System.out.println(first + "," + second);
for(int i: a) {
if(firstVote > 0 && i == first) firstCount++;
if(secondVote > 0 && i == second) secondCount++;
}
if(firstCount > a.length / 3) System.out.println(first);
if(secondCount > a.length / 3) System.out.println(second);
}
implement using an array and a HashMap that handle dupliates
ideone.com/rlrIuy
class RandomMap
{
private int size;
private int[] a;
private Map<Integer, List<Integer>> map;
private Random r;
public RandomMap(int capacity)
{
size = 0;
a = new int[capacity];
map = new HashMap<Integer, List<Integer>>();
r = new Random();
}
public int size()
{
return size;
}
// TODO: resize
public void add(int n)
{
int index = size++;
a[index] = n;
if(map.containsKey(n)) map.get(n).add(index);
else {
List<Integer> l = new ArrayList<Integer>();
l.add(index);
map.put(n, l);
}
}
public void remove(int n)
{
if(map.containsKey(n)) {
int p = map.get(n).get(0);
map.get(n).remove(0);
if(p != size - 1) {
int m = a[size - 1];
a[p] = m;
List<Integer> l2 = map.get(m);
for(int i = 0; i < l2.size(); i++) {
if(l2.get(i) == size - 1) {
l2.set(i, p);
break;
}
}
}
size--;
}
}
public int getRandom()
{
if(size > 1) return a[r.nextInt(size - 1)];
else if(size == 1) return a[0];
else throw new NoSuchElementException();
}
}
Time: O(mn)
public int[] min(int[][] a)
{
int total = 0;
int weightX = 0;
int weightY = 0;
int m = a.length;
int n = a[0].length;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
total += a[i][j];
weightX += a[i][j] * j;
weightY += a[i][j] * i;
}
}
int x = Math.round(weightX / total);
int y = Math.round(weightY / total);
return new int[] {x, y};
}
Time: O(nlgn)
Space: O(n)
public void arrange(int[] a, int[] b, int i, int j)
{
if(j == i) return;
for(int k = i; k <= j; k++) b[k] = a[k]; // copy the elements to the temporary array
int r = i + (j - i) / 2 + 1; // the pivot where the even half starts
int p = i; // the starting index of the odd half
int q = r; // the starting index of the even half
for(int k = i; k <= j; k++) {
if((k - i) % 2 == 0) a[p++] = b[k];
else a[q++] = b[k];
}
arrange(a, b, i, r - 1);
arrange(a, b, r, j);
}
nice algorithm!
java codes below
public int[] longestConsecutiveSequence(int[] a)
{
int first = Integer.MAX_VALUE; // the first number of the maximum consecutive sequence
int length = 0; // the length of the maximum consecutive sequence
Map<Integer, Integer> table = new HashMap<Integer, Integer>();
for(int i: a) {
if(!table.containsKey(i)) {
int start = i;
int end = i;
if(table.containsKey(i + 1) && table.get(i + 1) >= i + 1) {
end = table.get(i + 1);
table.remove(i + 1);
table.remove(end);
}
if(table.containsKey(i - 1) && table.get(i - 1) <= i - 1) {
start = table.get(i - 1);
table.remove(i - 1);
table.remove(start);
}
table.put(start, end);
table.put(end, start);
if(end - start + 1 > length) {
first = start;
length = end - start + 1;
}
}
}
System.out.println(table);
System.out.println(length);
int[] s = new int[length];
for(int i = 0; i < length; i++) s[i] = first + i;
return s;
}
Algorithm
maintain the starting index of the minimum string and the ending index from the start, which contains duplicate characters with the substring ending at the current index
if the character at the current index is equal to the character at the ending index, increment the ending index
if the character at the current index is smaller than the character at the ending index, set the ending index to zero
if the character at the current index is bigger than the character at the ending index, set the start to the index where the duplicate substring ending at the current index starts
Time: O(n)
public String minString(String a)
{
int n = a.length();
int start = 0; // the starting index of the minimum string
int i = 0; // the ending index from start, which contains duplicate characters
for(int k = 1; k < n || i % n > 0 ; k++) {
if(a.charAt((start + i) % n) == a.charAt((start + k) % n)) {
i++;
} else if(a.charAt((start + i) % n) < a.charAt((start + k) % n)) {
i = 0;
} else {
start = (start + k - i) % n;
k = (k - i - 1) % n;
i = 0;
}
}
return a.substring(start) + a.substring(0, start);
}
only join the string once
public String join(String a, String b)
{
for(int i = 0; i < a.length() + b.length(); i++) {
char c1 = i < a.length() ? a.charAt(i) : b.charAt(i - a.length());
char c2 = i < b.length() ? b.charAt(i) : a.charAt(i - b.length());
if (c1 < c2)
return b + a;
else if (c1 > c2)
return a + b;
}
return b + a;
}
Optimal Structure
p(i, j) = min{A[i] * A[j] + p(i - 1, j - 1), 0 * A[j] + p(i, j - 1)}
Algorithm
t[i][j] store the minimum multiplication formed by a[i] and b[j]
ideone.com/squ8Qw
public int min(int[] a, int[] b)
{
int m = a.length;
int n = b.length;
// the minimum multiplication formed by the subarrays a[i] and b[j]
int[][] t = new int[m][n];
for(int i = 0; i < m; i++) {
for(int j = i; j < i + (n - m) + 1; j++) {
if(j > 0) {
if(i > 0) t[i][j] = Math.min(a[i] * b[j] + t[i - 1][j - 1], t[i][j - 1]);
else t[i][j] = Math.min(a[i] * b[j], t[i][j - 1]);
} else {
t[i][j] = a[i] * b[j];
}
}
}
// construct the array with zeros
int[] c = new int[n];
int i = m - 1; // the pointer of the array a
int j = n - 1; // the pointer of the array b
int k = n - 1; // the pointer of the array c
for(; i >= 0 && j >= 0; j--) {
// set a[i] to c[k]
if(j == 0 || t[i][j] < t[i][j - 1]) c[k--] = a[i--];
// set 0 to c[k]
else c[k--] = 0;
}
System.out.println(Arrays.toString(c));
System.out.println(Arrays.toString(b));
return t[m - 1][n - 1];
}
Test Case
Onput
-2 1
2 5 3 1 6
-1
5 8 3
1 -1
1 2 3 4
Output
[0, -2, 0, 1, 0]
[2, 5, 3, 1, 6]
-9
[0, -1, 0]
[5, 8, 3]
-8
[1, 0, 0, -1]
[1, 2, 3, 4]
-3
public int minGap(int[] a, int[] b, int[] c)
{
int diff = Integer.MAX_VALUE;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int i, j, k;
for(i = 0, j = 0, k = 0; i < a.length && j < b.length && k < c.length;) {
min = Math.min(a[i], Math.min(b[j], c[k]));
max = Math.max(a[i], Math.max(b[j], c[k]));
diff = Math.min(diff, max - min);
if(diff == 0) break;
if(a[i] == min) i++;
else if(b[j] == min) j++;
else k++;
}
return diff;
}
generate the numbers with i set bits not greater than n from 2 ^ i - 1
ideone.com/qajp85
public int[] sort(int n)
{
int[] a = new int[n];
int k = 0;
for(int i = 1; i <= n; i = ((i + 1) << 1) - 1)
for(int j = i; j <= n; j = next(j))
a[k++] = j;
return a;
}
private int next(int n)
{
//n 1 0001 1100
//s 0 0000 0100 n & (-n)
//r 1 0010 0000 n + s
//ones 0 0011 1100 n ^ r
//ones 0 0000 0011 (ones >> 2) / s
//return 1 0010 0011 r + ones
int smallest = n & (-n);
int ripple = n + smallest;
int ones = n ^ ripple;
ones = (ones >> 2) / smallest;
return ripple + ones;
}
use a stack to store the function not returned, if read a log entry that a function starts, push the entry. if read a log entry that a function ends, pop up an entry from the stack
when read an entry and the current running function is "foo" by checking whether the top element of the stack, add the time difference between the current entry and the previous one to the total
Time: O(n)
Pseudo Codes
enum Type
{
START,
END
};
class LogEntry
{
public DateTime timeStamp;
public String function;
public Type type;
}
public int getElapse(List<LogEntry> log, String function)
{
int elapse = 0;
Stack<LogEntry> s = new Stack<LogEntry>();
for(int i = 0; i < log.size(); i++) {
LogEntry entry = log.get(i);
if(!s.empty() && s.peek().function.equals(function)) {
elapse += entry.timeStamp - log.get(i - 1).timeStamp;
}
if(entry.type == Type.END && s.peek().type == Type.Start && entry.function.equals(s.peek().function)) {
s.pop();
} else {
s.push(entry);
}
return elapse;
}
class Point{
public double x;
public double y;
public Point(double x, double y)
{
this.x = x;
this.y = y;
}}
class Line{
private Point p1;
private Point p2;
private double slope;
private double intercept;
public Line(Point p1, Point p2)
{
this.p1 = p1;
this.p2 = p2;
slope = (p1.y - p2.y) / (p1.x - p2.x);
intercept = p1.x - p1.y / slope;
}
public boolean contains(Point pt)
{
if(slope == Double.NEGATIVE_INFINITY || slope == Double.POSITIVE_INFINITY) return pt.x == p1.x;
else return p1.y - slope * (p1.x - pt.x) == pt.y;
}
public double getSlope()
{
return slope;
}
public double getIntercept()
{
return intercept;
}}
public Line getLine(List<Point> points)
{
Line line = null;
int max = -1;
int n = points.size();
for(int i = 0; i < n - 1; i++) {
for(int j = i + 1; j < n; j++) {
Line l = new Line(points.get(i), points.get(j));
int m = 0;
for(int k = j + 1; k < n; k++)
if(l.contains(points.get(k))) m++;
if(m > max) {
max = m;
line = l;
}
}
}
return line;
}
if n is odd, start from (n-1, n-1) and set the element clock wisely from n^2 - 1 to zero in the order of top, right, bottom and left
if n is even, start from (0, 0) and set the element close wisely from n^2 - 1 to zero in the oder of bottom, left, top and right
Dijkstra Algorithm
ideone.com/AgQ1e4
Point - represent a point with the total difficulty from the source
override the equals, hashCode and implement Comparable interface so that it can be put to the priority queue
calculate all points difficulty using Dijkstra algorithm
use an auxiliary array holding all points and a map which store the predecessor for each point
in the end construct the path using the predecessors map
class Point implements Comparable<Point>
{
public int x;
public int y;
public int d; //the total difficulty from the source
public Point(int x, int y)
{
this.x = x;
this.y = y;
this.d = Integer.MAX_VALUE;
}
@Override
public boolean equals(Object o)
{
Point pt = (Point)o;
return x == pt.x && y == pt.y;
}
@Override
public int hashCode()
{
return (17 + 31 * x) * 31 + y;
}
@Override
public String toString()
{
return "(" + x + ", " + y + ")";
}
@Override
public int compareTo(Point pt)
{
return d - pt.d;
}
}
public int minDifficulty(int[][] a)
{
int m = a.length;
int n = a[0].length;
Point[][] points = new Point[m][n];
Map<Point, Point> p = new HashMap<Point, Point>(); //the predecessor map
Queue<Point> q = new PriorityQueue<Point>();
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
Point pt = new Point(i, j);
points[i][j] = pt;
if(i == 0 && j == 0) pt.d = a[0][0];
p.put(pt, null);
q.offer(pt);
}
}
while(q.peek() != null) {
Point pt = q.poll();
//find adjacent points
List<Point> neighbours = new ArrayList<Point>();
for(int i = 0; i < m; i++) {
if(i != pt.x) neighbours.add(points[i][pt.y]);
}
for(int i = 0; i < n; i++) {
if(i != pt.y) neighbours.add(points[pt.x][i]);
}
for(Point neighbour: neighbours) {
//relax
if(q.contains(neighbour) && neighbour.d > pt.d + a[neighbour.x][neighbour.y]) {
q.remove(neighbour);
neighbour.d = pt.d + a[neighbour.x][neighbour.y];
p.put(neighbour, pt);
q.offer(neighbour);
}
}
}
//construct path
List<Point> path = new ArrayList<Point>();
for(Point pt = points[m - 1][n - 1]; pt != null; pt = p.get(pt)) path.add(0, pt);
System.out.println(path);
return points[m - 1][n - 1].d;
}
use a hash table to store digits and their occurrences instead of performing the binary search on the sorted array
first to choose the same digit for every position and recursively choose the next position with remaining digits
if it failed to yield a valid combination or the same digit doesn't exist, choose the next larger digit and arrange the position on left with remaining digits in the ascending order
if no lager digit, return false
Time: O(n)
ideone.com/8pDJIG
Test Cases
2 1 4 5
2 1 4 6
[2, 1, 5, 4]
1 6 7 3 2
6 7 8 9 1
[7, 1, 2, 3, 6]
1 2 3 4
2 4 3 9
[3, 1, 2, 4]
1 2 3 4
2 4 1 0
[2, 4, 1, 3]
4
1 3 3 4
4 3 2 1
[4, 3, 3, 1]
public void findClosestPermuntation(int[] x, int[] y)
{
int[] z = new int[x.length];
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < 10; i++) map.put(i, 0);
for(int i: x) map.put(i, map.get(i) + 1);
r(y, z, 0, map);
System.out.println(Arrays.toString(z));
}
private boolean r(int[] y, int[] z, int i, Map<Integer, Integer> map)
{
if(i == z.length) return true;
int j;
for(j = y[i]; j < 10 && map.get(j) == 0; j++);
if(j == y[i]) {
z[i] = y[i];
map.put(j, map.get(j) - 1);
if(r(y, z, i + 1, map)) return true;
map.put(j, map.get(j) + 1);
z[i] = 0;
for(j = y[i] + 1; j < 10 && map.get(j) == 0; j++);
}
if(j > 9) return false;
z[i] = j;
map.put(j, map.get(j) - 1);
int k = i + 1;
for(int p = 0; p < 10; p++) {
for(int q = 0; q < map.get(p); q++) {
z[k] = p;
k++;
}
}
return true;
}
solution 1
use HashSet as suggested
solution 2
sort one array and binary search every element in another array
solution 3
sort both arrays, traverse them at the same time and add the same element
public ArrayList<Integer> intersect(ArrayList<Integer> a, ArrayList<Integer> b)
{
ArrayList<Integer> c = new ArrayList<Integer>();
int i = 0;
int j = 0;
while(i < a.size() && j < b.size()) {
for(; i < a.size() && j < b.size() && a.get(i) < b.get(j); i++);
for(; j < b.size() && i < a.size() && b.get(j) < a.get(i); j++);
if(i < a.size() && j < b.size() && a.get(i) == b.get(j)) {
c.add(a.get(i));
i++;
j++;
}
}
return c;
}
public void sort(Integer[] a)
{
Arrays.sort(a, new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b)
{
if(a == 0) return b;
else if(b == 0) return a;
else return concat(b, a) - concat(a, b);
}
private int concat(Integer a, Integer b)
{
return (int)(a * Math.pow(10, ((int)Math.floor(Math.log10(b)) + 1)) + b);
}
});
}
find the index (k) of the smallest number within the [0..n) (excluding n) and put the smallest number at the last position
find the index (k) of the smallest number within the range [0..n-1) and put the smallest number at the last position
...
find the index (k) of the smallest number within the range [0..n-i) and put the smallest number at the last position
...
find the index (k) of the smallest number within the range [0..1) and put the smallest number at the last position
Time: O(n^2)
public void sort(int[] a)
{
for(int i = 0; i < n; i++) {
int k = 0;
for(int j = 1; j < n - i; j++) {
if(a[j] < a[k]) k = j;
}
arrange(a, k);
}
}
similar as finding the diameter of the tree, recursively find out the max sum of the path in the left or right subtree and max sum of the path from the left child or right child
max = max(val + (left_max_from_root > 0 ? left_max_from_root : 0) + (right_max_from_root > 0 ? right_max_from_root : 0),
left_max,
right_max)
max_from_root = max(val, left_max_from_root + val, right_max_from_root + val)
class MaxSum
{
public int max; //max sum of the path in the tree (not necessary includind the root)
public int maxFromRoot; //max sum of the path from the root (not necessary to the leaf node)
public MaxSum(int max, int maxFromRoot)
{
this.max = max;
this.maxFromRoot = maxFromRoot;
}
}
public MaxSum maxSum(TreeNode root)
{
if(root == null) return new MaxSum(0, 0);
MaxSum leftSum = maxSum(root.left);
MaxSum rightSum = maxSum(root.right);
int maxFromRoot = Math.max(root.val, Math.max(leftSum.maxFromRoot + root.val, rightSum.maxFromRoot + root.val));
int max = root.val +
(leftSum.maxFromRoot > 0 ? leftSum.maxFromRoot : 0) +
(rightSum.maxFromRoot > 0 ? rightSum.maxFromRoot : 0);
max = Math.max(max, Math.max(leftSum.max, rightSum.max));
return new MaxSum(max, maxFromRoot);
}
public void threeWayPartition(int[] a, int pivot)
{
int p = 0;
int q = a.length - 1;
for(int i = 0; i <= q;) {
if(a[i] < pivot) swap(a, i++, p++);
else if(a[i] > pivot) swap(a, i, q--);
else i++;
}
}
private void swap(int[] a, int i, int j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
class BigInteger
{
private ArrayList<Character> digits;
public BigInteger(String s)
{
digits = new ArrayList<Character>();
char[] a = s.toCharArray();
for(int i = a.length - 1; i >= 0; i--) digits.add(a[i]);
}
public void increment()
{
int i = 0;
for(; i < digits.size() && digits.get(i) == '9'; i++) digits.set(i, '0');
if(i < digits.size()) digits.set(i, (char)(digits.get(i) + 1));
else digits.add('1');
}
public void decrement()
{
int i = 0;
for(; i < digits.size() && digits.get(i) == '0'; i++) digits.set(i, '9');
digits.set(i, (char)(digits.get(i) - 1));
if(i == digits.size() - 1 && digits.get(i) == '0') digits.remove(i);
}
@Override
public String toString()
{
StringBuilder sb = new StringBuilder();
for(int i = digits.size() - 1; i >= 0; i--)
sb.append(digits.get(i));
return sb.toString();
}
}
we've to find all possible words and check if the dictionary contains a particular word
public void findWords(char[][] a)
{
words.clear();
int m = a.length;
int n = a[0].length;
boolean[][] b = new boolean[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
findWords(a, b, "", i, j);
}
}
System.out.println(words);
}
private void findWords(char[][] a, boolean[][] b, String word, int i , int j)
{
if(i < 0 || i >= a.length || j < 0 || j >= a[i].length || b[i][j]) return;
String word1 = word + Character.toString(a[i][j]);
if(dict.contains(word1)) words.add(word1);
boolean[][] b1 = new boolean[b.length][b[0].length];
for(int p = 0; p < b.length; p++)
for(int q = 0; q < b[p].length; q++)
b1[p][q] = b[p][q];
b1[i][j] = true;
findWords(a, b1, word1, i - 1, j);
findWords(a, b1, word1, i + 1, j);
findWords(a, b1, word1, i, j - 1);
findWords(a, b1, word1, i, j + 1);
}
private static List<String> words = new ArrayList<String>();
private static Set<String> dict = new HashSet<String>();
it is not necessary to convert the dictionary to a tire as the problem states that it's efficient to check whether a word present
also the dictionary could contains huge number of words and tire is space consuming
the more critical part of this problem is to get all possible words. it can be done either by BFS or DFS
RepSpent high school summers donating toy monkeys in Minneapolis, MN. At the moment I'm building glue in Edison, NJ ...
Check a[n/4] and a[n/2] and a[3*n/4] occurrence
- dgbfs February 26, 2015Checking the occurrence takes O(lgn) time