Question

1436. Destination City

中文文档

Description

You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBi. _Return the destination city, that is, the city without any path outgoing to another city._

It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.

 

Example 1:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo" 
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

Example 2:

Input: paths = [["B","C"],["D","B"],["C","A"]]
Output: "A"
Explanation: All possible trips are: 
"D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
Clearly the destination city is "A".

Example 3:

Input: paths = [["A","Z"]]
Output: "Z"

 

Constraints:

• 1 <= paths.length <= 100
• paths[i].length == 2
• 1 <= cityAi.length, cityBi.length <= 10
• cityAi != cityBi
• All strings consist of lowercase and uppercase English letters and the space character.

Solutions

Solution 1

class Solution:
  def destCity(self, paths: List[List[str]]) -> str:
    s = {a for a, _ in paths}
    return next(b for _, b in paths if b not in s)

class Solution {
  public String destCity(List<List<String>> paths) {
    Set<String> s = new HashSet<>();
    for (var p : paths) {
      s.add(p.get(0));
    }
    for (var p : paths) {
      if (!s.contains(p.get(1))) {
        return p.get(1);
      }
    }
    return "";
  }
}

class Solution {
public:
  string destCity(vector<vector<string>>& paths) {
    unordered_set<string> s;
    for (auto& p : paths) {
      s.insert(p[0]);
    }
    for (auto& p : paths) {
      if (!s.count(p[1])) {
        return p[1];
      }
    }
    return "";
  }
};

func destCity(paths [][]string) string {
  s := map[string]bool{}
  for _, p := range paths {
    s[p[0]] = true
  }
  for _, p := range paths {
    if !s[p[1]] {
      return p[1]
    }
  }
  return ""
}

function destCity(paths: string[][]): string {
  const set = new Set(paths.map(([a]) => a));
  for (const [_, b] of paths) {
    if (!set.has(b)) {
      return b;
    }
  }
  return '';
}

use std::collections::HashSet;
impl Solution {
  pub fn dest_city(paths: Vec<Vec<String>>) -> String {
    let set = paths
      .iter()
      .map(|v| &v[0])
      .collect::<HashSet<&String>>();
    for path in paths.iter() {
      if !set.contains(&path[1]) {
        return path[1].clone();
      }
    }
    String::new()
  }
}

/**
 * @param {string[][]} paths
 * @return {string}
 */
var destCity = function (paths) {
  const s = new Set();
  for (const [a, _] of paths) {
    s.add(a);
  }
  for (const [_, b] of paths) {
    if (!s.has(b)) {
      return b;
    }
  }
  return '';
};

char* destCity(char*** paths, int pathsSize, int* pathsColSize) {
  for (int i = 0; i < pathsSize; i++) {
    int flag = 1;
    for (int j = 0; j < pathsSize; j++) {
      if (strcmp(paths[i][1], paths[j][0]) == 0) {
        flag = 0;
        break;
      }
    }
    if (flag) {
      return paths[i][1];
    }
  }
  return NULL;
}