By the way, does anyone know the time complexity of using UnionFind?
J
jie27
@jie27
36
Reputation
5
Posts
95
Profile views
0
Followers
0
Following
Posts made by jie27

RE: Java Union Find Solution

RE: Java Union Find Solution
You only need to do it for two directions, which are "right" and "down", because all "left" and "up" has already been seen if exists connection (undirected for Union Find).

Share my Java AC solution, O(1) space, one forloop, no string concatenation
public class Solution { public boolean isOneEditDistance(String s, String t) { int m = s.length(), n = t.length(); if (m > n) // s is the shorter one return isOneEditDistance(t, s); if (m + 1 < n) return false; int count = 0; for (int i = 0, j = 0; j < n; i++, j++) { if (i == m) { count++; continue; } if (s.charAt(i) == t.charAt(j)) continue; count ^= 1; if (count == 0) return false; if (m < n) i; } return count == 1; } }

RE: C++ very simple and easy understand. using bit operation
Wow that's brilliant!!!
Thank you so much for providing such a nice solution! 
My iterative 364ms Java solution
See below:
public int[] searchRange(int[] nums, int target) { int[] range = {1, 1}; if (nums == null  nums.length == 0) return range; int low = 0; int high = nums.length  1; int mid = 0; boolean flag = false; while (low <= high) { mid = (low + high) / 2; if (nums[mid] == target) { flag = true; break; } else if (nums[mid] > target) { high = mid  1; } else { low = mid + 1; } } if (!flag) return range; range[0] = mid; range[1] = mid; int temphigh = high; int tempmid = mid; high = mid  1; // search for the low end while (low <= high) { mid = (low + high) / 2; if (nums[mid] == target) { range[0] = mid; high = mid  1; } else if (nums[mid] > target) { high = mid  1; } else { low = mid + 1; } } high = temphigh; mid = tempmid; low = mid + 1; // search for the high end while (low <= high) { mid = (low + high) / 2; if (nums[mid] == target) { range[1] = mid; low = mid + 1; } else if (nums[mid] > target) { high = mid  1; } else { low = mid + 1; } } return range; }