首页 > 代码库 > 利用拓扑排序求一些字符串中的偏序关系。
利用拓扑排序求一些字符串中的偏序关系。
题意：给出一些字符串，默认所有字符间存在着某种偏序（如果输入满足时，为良序）关系，如{"free", "gbk", "atoi"}，每一个字符串中排在前面的字符总是小于等于排在后面的字符。
解题思路是把每一个字符串中任意两个相邻字符看做是<=的偏序关系，建立一个图，在对这个图做一次拓扑排序。
拓扑排序的两种常见的算法：1. 利用入度为0，使用队列来处理； 2. 利用dfs将节点按出栈顺序逆序输出。
public class Solution{ private static boolean myGraph[][]; private static boolean valid[]; private static void buildMap(String sortedSequence[]) { myGraph = new boolean[128][128]; valid = new boolean[128]; // initial my graph for (int i = 0; i < sortedSequence.length; ++i) { valid[sortedSequence[i].charAt(0)] = true; for (int j = 1; j < sortedSequence[i].length(); ++j) { valid[sortedSequence[i].charAt(j)] = true; if (sortedSequence[i].charAt(j - 1) != sortedSequence[i] .charAt(j)) { myGraph[sortedSequence[i].charAt(j - 1)][sortedSequence[i] .charAt(j)] = true; } } } } // solve by using a queue public static String solve_0(String sortedSequence[]) { buildMap(sortedSequence); // topological sort java.util.Queue<Integer> auxQueue = new java.util.LinkedList<Integer>(); int inDegrees[] = new int[128]; int chars = 0; for (int i = 1; i < 128; ++i) { chars += valid[i] ? 1 : 0; } for (int i = 1; i < 128; ++i) { if (valid[i]) { for (int j = 1; j < 128; ++j) { if (i != j && myGraph[i][j]) { ++inDegrees[j]; } } } } for (int i = 1; i < 128; ++i) { if (valid[i] && inDegrees[i] == 0) { auxQueue.add(i); } } String ret = ""; while (!auxQueue.isEmpty()) { int cur = auxQueue.remove(); ret += (char) cur; for (int i = 1; i < 128; ++i) { if (cur != i && myGraph[cur][i]) { if (--inDegrees[i] == 0) { auxQueue.add(i); } } } } return ret.length() == chars ? ret : null; } private enum color { WHITE, GRAY, BLACK, DISAPPEARED }; // solve by dfs public static String solve_1(String sortedSequence[]) { java.util.Stack<Integer> auxStack = new java.util.Stack<Integer>(); color charColor[] = new color[128]; for(int i = 1; i < 128; ++i) { charColor[i] = color.WHITE; } String ans = ""; for (int k = 1; k < 128; ++k) { if (valid[k] && charColor[k] == color.WHITE) { charColor[k] = color.GRAY; auxStack.push(k); while (!auxStack.isEmpty()) { int cur = auxStack.peek(); if (charColor[cur] == color.GRAY) { charColor[cur] = color.BLACK; for (int i = 1; i < 128; ++i) { if (valid[i] && cur != i && myGraph[cur][i]) { if (charColor[i] == color.BLACK)// back edge { return null; } if(charColor[i] == color.WHITE) { charColor[i] = color.GRAY; auxStack.push(i); } } } } else { ans = (char)cur + ans; auxStack.pop(); charColor[cur] = color.DISAPPEARED; } } } } return ans; } public static void main(String[] args) { String[] A = { "ft", "fcp", "aac", "act", "acd", "atp", "tbk", "tfd" }; System.out.println(solve_0(A)); System.out.println(solve_1(A)); }}
利用拓扑排序求一些字符串中的偏序关系。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。