Given an array of strings, find if the strings can be chained to form a circle | GeeksforGeeks
Given an array of strings, find if the given strings can be chained to form a circle. A string X can be put before another string Y in circle if the last character of X is same as first character of Y.
The edges represents one word, vertexes can be shared.
#define CHARS 26
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/ChainWordsToFormCircle.java
public List<String> formCircle(String input[]){
List<String> result = new ArrayList<String>();
//since chain is a circle any point can be the start point of the chain.
//We make input[0] as start point
result.add(input[0]);
boolean used[] = new boolean[input.length];
boolean r = formCircle(input,result,used,input[0].charAt(0));
if(!r){
return Collections.emptyList();
}
return result;
}
//we keep track of first char of the chain and the end compare that with last char of last element of the chain
private boolean formCircle(String input[], List<String> result,boolean used[],char firstChar){
if(input.length == result.size()){
String str = result.get(result.size()-1);
if(firstChar == str.charAt(str.length()-1)){
return true;
}
return false;
}
String str = result.get(result.size()-1);
char lastChar = str.charAt(str.length()-1);
for(int i=1; i < input.length; i++){
if(used[i]){
continue;
}
if(lastChar == input[i].charAt(0)){
used[i] = true;
result.add(input[i]);
boolean r = formCircle(input,result,used,firstChar);
if(r){
return true;
}
used[i] = false;
result.remove(result.size()-1);
}
}
return false;
}
Eulerian path and circuit for undirected graph
http://www.geeksforgeeks.org/eulerian-path-and-circuit/
Euler Circuit in a Directed Graph
http://www.geeksforgeeks.org/euler-circuit-directed-graph/
A directed graph has an eulerian cycle if following conditions are true (Source: Wiki)
1) All vertices with nonzero degree belong to a single strongly connected component. //one dfs and one dfs for its transpose graph
2) In degree and out degree of every vertex is same. // do this fisrt
https://reeestart.wordpress.com/2016/06/14/gfg-check-if-strings-can-be-chained-to-form-a-cycle/
http://www.geeksforgeeks.org/find-array-strings-can-chained-form-circle-set-2/
We solve this problem by treating this as a graph problem, where vertices will be first and last character of strings and we will draw an edge between two vertices if they are first and last character of same string, so number of edges in graph will be same as number of strings in the array.
X. Extend
https://reeestart.wordpress.com/2016/06/14/google-longest-string-pair-that-forms-a-cycle/
Read full article from Given an array of strings, find if the strings can be chained to form a circle |
GeeksforGeeks
Given an array of strings, find if the given strings can be chained to form a circle. A string X can be put before another string Y in circle if the last character of X is same as first character of Y.
The idea is to create a graph of all characters and then find if their is an eulerian circuit in the graph or not. If there is an eulerian circuit, then chain can be formed, otherwise not.
Note that a graph has eulerian circuit only if all vertices are of even degree.
Note that a graph has eulerian circuit only if all vertices are of even degree.
Following are detailed steps of the algorithm.
1) Create a graph g with number of vertices equal to the size of alphabet in the given alien language. We have created a graph with 26 vertices in the below program.
2) Do following for every string in the given array of strings.
…..a) Add an edge from first character to last character of the given graph.
…..a) Add an edge from first character to last character of the given graph.
3) If the created graph has eulerian circuit, then return true, else return false.
bool canBeChained(string arr[], int n){ // Create a graph with 'aplha' edges Graph g(CHARS); // Create an edge from first character to last character // of every string for (int i = 0; i < n; i++) { string s = arr[i]; g.addEdge(s[0]-'a', s[s.length()-1]-'a'); } // The given array of strings can be chained if there // is an eulerian cycle in the created graph return g.isEulerianCycle();}class Graph{ int V; // No. of vertices list<int> *adj; // A dynamic array of adjacency listsvoid Graph::addEdge(int v, int w){ adj[v].push_back(w); adj[w].push_back(v); // Note: the graph is undirected}/* This function returns true if the graph has an eulerian
cycle, otherwise returns false */
bool Graph::isEulerianCycle()
{
// Check if all non-zero degree vertices are connected
if (isConnected() == false)
return 0;
// Check if there is a vertex with odd degree
for (int i = 0; i < V; i++)
if (adj[i].size() & 1)
return false;
return true; // If all vertices are of even degree
}
bool Graph::isConnected(){ // Mark all the vertices as not visited bool visited[V]; int i; for (i = 0; i < V; i++) visited[i] = false; // Find a vertex with non-zero degree for (i = 0; i < V; i++) if (adj[i].size() != 0) break; // If there are no edges in the graph, return true if (i == V) return true; // Start DFS traversal from a vertex with non-zero degree DFSUtil(i, visited); // Check if all non-zero degree vertices are visited for (i = 0; i < V; i++) if (visited[i] == false && adj[i].size() > 0) return false; return true;}public List<String> formCircle(String input[]){
List<String> result = new ArrayList<String>();
//since chain is a circle any point can be the start point of the chain.
//We make input[0] as start point
result.add(input[0]);
boolean used[] = new boolean[input.length];
boolean r = formCircle(input,result,used,input[0].charAt(0));
if(!r){
return Collections.emptyList();
}
return result;
}
//we keep track of first char of the chain and the end compare that with last char of last element of the chain
private boolean formCircle(String input[], List<String> result,boolean used[],char firstChar){
if(input.length == result.size()){
String str = result.get(result.size()-1);
if(firstChar == str.charAt(str.length()-1)){
return true;
}
return false;
}
String str = result.get(result.size()-1);
char lastChar = str.charAt(str.length()-1);
for(int i=1; i < input.length; i++){
if(used[i]){
continue;
}
if(lastChar == input[i].charAt(0)){
used[i] = true;
result.add(input[i]);
boolean r = formCircle(input,result,used,firstChar);
if(r){
return true;
}
used[i] = false;
result.remove(result.size()-1);
}
}
return false;
}
Eulerian path and circuit for undirected graph
http://www.geeksforgeeks.org/eulerian-path-and-circuit/
Eulerian Cycle
An undirected graph has Eulerian cycle if following two conditions are true.
….a) All vertices with non-zero degree are connected. We don’t care about vertices with zero degree because they don’t belong to Eulerian Cycle or Path (we only consider all edges). // one dfs
….b) All vertices have even degree. // We should do this step first. much faster.
An undirected graph has Eulerian cycle if following two conditions are true.
….a) All vertices with non-zero degree are connected. We don’t care about vertices with zero degree because they don’t belong to Eulerian Cycle or Path (we only consider all edges). // one dfs
….b) All vertices have even degree. // We should do this step first. much faster.
Eulerian Path
An undirected graph has Eulerian Path if following two conditions are true.
….a) Same as condition (a) for Eulerian Cycle
….b) If zero or two vertices have odd degree and all other vertices have even degree. Note that only one vertex with odd degree is not possible in an undirected graph (sum of all degrees is always even in an undirected graph)
An undirected graph has Eulerian Path if following two conditions are true.
….a) Same as condition (a) for Eulerian Cycle
….b) If zero or two vertices have odd degree and all other vertices have even degree. Note that only one vertex with odd degree is not possible in an undirected graph (sum of all degrees is always even in an undirected graph)
Euler Circuit in a Directed Graph
http://www.geeksforgeeks.org/euler-circuit-directed-graph/
A directed graph has an eulerian cycle if following conditions are true (Source: Wiki)
1) All vertices with nonzero degree belong to a single strongly connected component. //one dfs and one dfs for its transpose graph
2) In degree and out degree of every vertex is same. // do this fisrt
https://reeestart.wordpress.com/2016/06/14/gfg-check-if-strings-can-be-chained-to-form-a-cycle/
public boolean hasCircle(String[] words) { if (words.length == 0) { return false; } Map<Character, Set<Character>> graph = new HashMap<Character, Set<Character>>(); int[] inDegree = new int[26]; for (String str : words) { char first = str.charAt(0); char last = str.charAt(str.length() - 1); if (!graph.containsKey(first)) { graph.put(first, new HashSet<Character>()); } graph.get(first).add(last); inDegree[last - 'a']++; } return isEulerianCycle(graph, inDegree); } /* An directed graph has an Eulerian cycle if and only if every */ /* vertex has the indegree and outdegree */ private boolean isEulerianCycle(Map<Character, Set<Character>> graph, int[] inDegree) { if (!isStronglyConnect(graph)) { return false; } for (char c : graph.keySet()) { if (graph.get(c).size() != inDegree[c - 'a']) { return false; } } return true; } /* A directed graph is called strongly connected if there is a path in each direction between each pair of vertices of the graph */ private boolean isStronglyConnect(Map<Character, Set<Character>> graph) { boolean[] isVisited = new boolean[26]; for (char c : graph.keySet()) { if (graph.get(c).size() != 0) { dfs(c, graph, isVisited); break; } } for (char c : graph.keySet()) { if (!isVisited[c - 'a']) { return false; } } Map<Character, Set<Character>> reversedGraph = new HashMap<Character, Set<Character>>(); for (char ori : graph.keySet()) { for (char dest : graph.get(ori)) { if (!reversedGraph.containsKey(dest)) { reversedGraph.put(dest, new HashSet<Character>()); } reversedGraph.get(dest).add(ori); } } Arrays.fill(isVisited, false); for (char c : reversedGraph.keySet()) { if (reversedGraph.get(c).size() != 0) { dfs(c, reversedGraph, isVisited); break; } } for (char c : reversedGraph.keySet()) { if (!isVisited[c - 'a']) { return false; } } return true; } private void dfs(char c, Map<Character, Set<Character>> graph, boolean[] isVisited) { isVisited[c - 'a'] = true; for (char adj : graph.get(c)) { if (!isVisited[adj - 'a']) { dfs(adj, graph, isVisited); } } }http://www.geeksforgeeks.org/find-array-strings-can-chained-form-circle-set-2/
We solve this problem by treating this as a graph problem, where vertices will be first and last character of strings and we will draw an edge between two vertices if they are first and last character of same string, so number of edges in graph will be same as number of strings in the array.
Now it can be clearly seen after graph representation that if a loop among graph vertices is possible then we can reorder the strings otherwise not. As in above diagram’s example a loop can be found in first and third array of string but not in second array of string. Now to check whether this graph can have a loop which goes through all the vertices, we’ll check two conditions,
1) Indegree and Outdegree of each vertex should be same.
2) Graph should be strongly connected.
1) Indegree and Outdegree of each vertex should be same.
2) Graph should be strongly connected.
First condition can be checked easily by keeping two arrays, in and out for each character. For checking whether graph is having a loop which goes through all vertices is same as checking complete directed graph is strongly connected or not because if it has a loop which goes through all vertices then we can reach to any vertex from any other vertex that is, graph will be strongly connected and same argument can be given for reverse statement also.
Now for checking second condition we will just run a DFS from any character and visit all reachable vertices from this, now if graph has a loop then after this one DFS all vertices should be visited, if all vertices are visited then we will return true otherwise false so visiting all vertices in a single DFS flags a possible ordering among strings.
Now for checking second condition we will just run a DFS from any character and visit all reachable vertices from this, now if graph has a loop then after this one DFS all vertices should be visited, if all vertices are visited then we will return true otherwise false so visiting all vertices in a single DFS flags a possible ordering among strings.
// Utility method for a depth first search among verticesvoid dfs(vector<int> g[], int u, vector<bool> &visit){ visit[u] = true; for (int i = 0; i < g[u].size(); ++i) if(!visit[g[u][i]]) dfs(g, g[u][i], visit);}// Returns true if all vertices are strongly connected// i.e. can be made as loopbool isConnected(vector<int> g[], vector<bool> &mark, int s){ // Initialize all vertices as not visited vector<bool> visit(M, false); // perform a dfs from s dfs(g, s, visit); // now loop through all characters for (int i = 0; i < M; i++) { /* I character is marked (i.e. it was first or last character of some string) then it should be visited in last dfs (as for looping, graph should be strongly connected) */ if (mark[i] && !visit[i]) return false; } // If we reach that means graph is connected return true;}// return true if an order among strings is possiblebool possibleOrderAmongString(string arr[], int N){ // Create an empty graph vector<int> g[M]; // Initialize all vertices as not marked vector<bool> mark(M, false); // Initialize indegree and outdegree of every // vertex as 0. vector<int> in(M, 0), out(M, 0); // Process all strings one by one for (int i = 0; i < N; i++) { // Find first and last characters int f = arr[i].front() - 'a'; int l = arr[i].back() - 'a'; // Mark the characters mark[f] = mark[l] = true; // increase indegree and outdegree count in[f]++; out[l]++; // Add an edge in graph g[f].push_back(l); } // If for any character indegree is not equal to // outdegree then ordering is not possible for (int i = 0; i < M; i++) if (in[i] != out[i]) return false; return isConnected(g, mark, arr[0].front() - 'a');}X. Extend
https://reeestart.wordpress.com/2016/06/14/google-longest-string-pair-that-forms-a-cycle/
给一个 sorted dictionary, [about, apple, google, leg, lemma, time]
要求返回最长的一对pair，使得Pair中的两个单词满足：
第一个单词的最后两个字母等于第二个单词的头两个
第二个单词的最后一个字母等于第一个单词的头一个
第一个单词的最后两个字母等于第二个单词的头两个
第二个单词的最后一个字母等于第一个单词的头一个
就相当于形成一个cycle。
GFG – Check if Strings can be Chained to Form a Cycle 可以算这题的一个follow up。这题用hash map就可以搞定了，但是GFG这题还是比较难的。
[Solution]
最直接的办法就是用一个hash table来hash头两个字母以及单词。然后遍历一遍dict找最长的pair。这种做法时间复杂度为O(n)，空间也为O(n)。
最直接的办法就是用一个hash table来hash头两个字母以及单词。然后遍历一遍dict找最长的pair。这种做法时间复杂度为O(n)，空间也为O(n)。
不过注意题目写了是sorted dictionary. 如果被问到有没有其他方法？自然会想到binary search.
如果再仔细想想这道题的binary search并不能优化时间复杂度，反而降低了。只有在空间上有所提升。
[Solution #1] – binary search
对于每个字典里的string，根据它的最后两个字母，在整个字典里做binary search。
对于每个字典里的string，根据它的最后两个字母，在整个字典里做binary search。
但是当mid的头两个字母和curr的后两个字母一样时，不能直接丢掉左边或右边，得从mid开始往两边扫。所以这样binary search的时间复杂度为O(n), 即使用递归binary search, 递归式为T(n) = 2T(n / 2)，画个tree就知道也是O(n).
这样每个string做一遍binary search就是O(n^2).
不过递归binary search的代码不大写，值得好好看看。
[Solution #2] – hash table
// O(n^2) time, O(logn) spaceclass Solution { int result = 0; public int longestPair(String[] dict) { if (dict == null || dict.length == 0) { return 0; } for (String word : dict) { String end = word.substring(word.length() - 2, word.length()); char first = word.charAt(0); binarySearch(word, end, first, 0, dict.length - 1, dict); } return result; } private void binarySearch(String word, String start, char last, int l, int r, String[] dict) { if (l > r) { return; } while (l <= r) { int mid = (l + r) / 2; String curr = dict[mid]; if (curr.startsWith(start)) { if (curr.charAt(curr.length() - 1) == last) { result = Math.max(result, word.length() + curr.length()); } binarySearch(word, start, last, l, mid - 1, dict); binarySearch(word, start, last, mid + 1, r, dict); return; } else if (curr.substring(0, 2).compareTo(start) < 0) { l = mid + 1; } else { r = mid - 1; } } }}/* If the dict is not sorted, then HashMap is required O(n) time, O(n) space*/class Solution2 { public int longestPair(String[] dict) { if (dict == null || dict.length == 0) { return 0; } Map<String, List<Integer>> map = new HashMap<>(); for (int i = 0; i < dict.length; i++) { String word = dict[i]; int len = word.length(); if (len <= 2) continue; String key = word.substring(len - 2, len) + word.charAt(0); map.putIfAbsent(key, new ArrayList<>()); map.get(key).add(i); } int result = 0; for (int i = 0; i < dict.length; i++) { String word = dict[i]; int len = word.length(); String _key = word.substring(0, 2) + word.charAt(word.length() - 1); if (map.containsKey(_key)) { for (int j : map.get(_key)) { result = Math.max(result, len + dict[j].length()); } } } return result; }}GeeksforGeeks
