Closed ErdemT09 closed 3 years ago
Both solutions are quite brilliant Erdem.
For the Deque solution:
I strongly recommend introducing a City
class instead of utilizing nested lists, in order to make it easy-to-understand and clear.
I refactored the code a little bit, but it would be better if you look over it again, as there might be some other codes that become obsolete after the new settings.
class Solution {
public List<Integer> mostSimilar(int n, int[][] roads, String[] names, String[] targetPath) {
int t = targetPath.length;
if (t == 0) {
return new ArrayList<>();
}
int[][] graph = createGraph(n, roads);
Deque<City> paths = new ArrayDeque<>();
setPathStarts(n, names, targetPath, paths);
return buildPathWithQueue(graph, paths, names, targetPath, n);
}
private List<Integer> buildPathWithQueue(int[][] graph, Deque<City> paths, String[] names, String[] targetPath,
int n) {
int t = targetPath.length;
boolean[][] seen = new boolean[n][t];
while (!paths.isEmpty()) {
City city = paths.poll();
List<Integer> currPathNodes = city.currPathNodes;
int length = currPathNodes.size();
if (length == t) {
return currPathNodes;
}
List<Integer> nextPathNodes;
for (int neighbor : graph[city.cityIndex]) {
if (seen[neighbor][length] == true) {
continue;
}
seen[neighbor][length] = true;
nextPathNodes = new ArrayList<>(currPathNodes);
nextPathNodes.add(neighbor);
City nextPath = new City(neighbor, nextPathNodes);
if (names[neighbor].equals(targetPath[length])) {
paths.addFirst(nextPath);
} else {
paths.addLast(nextPath);
}
}
}
return new ArrayList<>();
}
private void setPathStarts(int n, String[] names, String[] targetPath, Deque<City> q) {
for (int i = 0; i < n; i++) {
List<Integer> list = new ArrayList<>();
list.add(i);
City initialCity = new City(i, list);
if (targetPath[0].equals(names[i])) {
q.addFirst(initialCity);
} else {
q.addLast(initialCity);
}
}
}
private int[][] createGraph(int n, int[][] roads) {
int[][] graph = new int[n][];
int[] adjacentCount = new int[n];
for (int[] road : roads) {
adjacentCount[road[0]]++;
adjacentCount[road[1]]++;
}
for (int i = 0; i < n; i++) {
graph[i] = new int[adjacentCount[i]];
}
int[] currIdx = new int[n];
for (int[] road : roads) {
graph[road[0]][currIdx[road[0]]++] = road[1];
graph[road[1]][currIdx[road[1]]++] = road[0];
}
return graph;
}
private class City{
City(int cityIndex, List<Integer> currPathNodes){
this.cityIndex = cityIndex;
this.currPathNodes = currPathNodes;
}
int cityIndex;
List<Integer> currPathNodes;
}
}
Changes added.
We can apply your graph
idea for the DP solution in order to prevent traversing all the elements in the names
array to ask if they are adjacent.
Graph array can be considered as an adjacency matrix.
It would fasten the code remarkably.
Therefore, we can refactor like this:
class Solution {
int n;
String[] names;
String[] targetPath;
int targetLength;
int[][] distancesAtCities;
int[][] graph;
public List<Integer> mostSimilar(int n, int[][] roads, String[] names, String[] targetPath) {
this.n = n;
this.names = names;
this.targetPath = targetPath;
graph = createGraph(n, roads);
targetLength = targetPath.length;
distancesAtCities = new int[targetLength][n];
setLastDistances();
calculateDistancesBackwards();
return evaluateMostSimilarPath();
}
private int[][] createGraph(int n, int[][] roads) {
int[][] graph = new int[n][];
int[] adjacentCount = new int[n];
for (int[] road : roads) {
adjacentCount[road[0]]++;
adjacentCount[road[1]]++;
}
for (int i = 0; i < n; i++) {
graph[i] = new int[adjacentCount[i]];
}
int[] currIdx = new int[n];
for (int[] road : roads) {
graph[road[0]][currIdx[road[0]]++] = road[1];
graph[road[1]][currIdx[road[1]]++] = road[0];
}
return graph;
}
private void setLastDistances() {
String targetCity = targetPath[targetLength - 1];
for (int i = 0; i < n; i++) {
String curCity = names[i];
if (!targetCity.equals(curCity)) {
distancesAtCities[targetLength - 1][i] = 1;
}
}
}
private void calculateDistancesBackwards() {
String targetCity;
for (int t = targetLength - 2; t >= 0; t--) {
targetCity = targetPath[t];
for (int c = 0; c < n; c++) {
String curCity = names[c];
if (!curCity.equals(targetCity)) {
distancesAtCities[t][c] = 1;
}
int minNextValue = Integer.MAX_VALUE;
for (int nextCity : graph[c]) {
minNextValue = Math.min(distancesAtCities[t + 1][nextCity], minNextValue);
}
distancesAtCities[t][c] += minNextValue;
}
}
}
private List<Integer> evaluateMostSimilarPath() {
List<Integer> mostSimilarPath = new ArrayList<>(targetLength);
int prevCity = 0;
for (int i = 1; i < n; i++) {
if (distancesAtCities[0][i] < distancesAtCities[0][prevCity]) {
prevCity = i;
}
}
mostSimilarPath.add(prevCity);
addNextVertices(mostSimilarPath, prevCity, 1);
return mostSimilarPath;
}
private void addNextVertices(List<Integer> mostSimilarPath, int prevCity, int idx) {
if (idx == targetLength) {
return;
}
int curMinCity = -1;
int curMinDist = Integer.MAX_VALUE;
for (int nextCity : graph[prevCity]) {
if (distancesAtCities[idx][nextCity] < curMinDist) {
curMinDist = distancesAtCities[idx][nextCity];
curMinCity = nextCity;
}
}
mostSimilarPath.add(curMinCity);
addNextVertices(mostSimilarPath, curMinCity, idx + 1);
}
}
It would fasten the code remarkably.
I thought adjacency matrix was okay, since it was only booleans, even in terms of time needed. The graphing makes it about twice as fast though.
Resolves: #215
Approach 1-Dynamic Programming:
We should notice the recurrence relation: The most similar path of length
T
is the concatenation of some cityc==targetPath[0]
and the most similar path that can start from that city, of lengthT-1
. Written in dynamic programming form:dp[t][c] = min{dp[t+1][next]} + targetPath[t] == c ? 0 : 1
, wheret
is the index of the target path we are considering andnext
∈ All cities connected toc
. We can first calculatedp[lastIndex][c]
for all cities.dp[lastIndex-1][c]
would then be equal to minimum ofdp[lastIndex][next]
for all cities connectedc
(of course, added with 1 or 0 for the edit distance). We can thus loop our way back to the 0th index.After that, we create the path simply by retracing the dp array with the minimum values and the previous city we visited.
Approach 2-Priority Queue Implemented with Double-ended Queue:
Here, it is naturally intuitive to place all the paths in a priority queue and keep poll out the one with the least edit distance. However, since we are allowed to return back to the same node after visiting it, this approach would render inefficient with a possible worst case complexity of
O(p·log p)
,p=number of paths
. We won't get the benefits that an algorithm like Dijkstra's would have, as we can't have anything like distance array. So, the most convenient option is to use a dequeue as a sort of a priority queue. Each time, if some node on the path is equal to its corresponding name in thetargetPath
, we put its new path on the start of the queue, else we put it to the end of the queue. We remove paths from the queue by removing the first element, so the relatively best path. At the end, we would poll out the path with the length of thetargetPath
that is the most similar. I won't try to prove this, it's however pretty intuitive.