检查是否可以通过字符串数组链形成一个环（Java）

2024年9月10日 | 阅读 6 分钟

查找字符串数组是否可以链接在一起形成一个环。如果字符串X的最后一个字符和字符串Y的第一个字符相同，则字符串X可以放置在字符串Y之前的环中。

示例 1

输入

字符串a = {"python", "nodejs", "scripted-php"}

输出

是的，这些字符串可以连接形成一个环。

解释

对于给定的字符串数组，可以形成链的字符串是 python ? nodejs; nodejs ? scripted-php; scripted-php ? python。因此，这些字符串可以连接形成一个环。

示例 2

输入

字符串a = {"bac", "cda", "aaa", "aab"}

输出

是的，这些字符串可以连接形成一个环。

解释

对于给定的字符串数组，可以形成链的字符串是 bac ? cda; cda ? aaa; aaa ? aab; aab ? bac。因此，这些字符串可以连接形成一个环。

示例 3

输入

字符串a = {"ijk", "kji", "abc", "cba"}

输出

否，这些字符串不能连接形成一个环。

解释

对于给定的字符串数组，可以形成链的字符串是 ijk ? kji; abc ? cba，但它们不能形成一个环。因此，这些字符串不能连接形成一个环。

方法：使用有向图

该方法将一个算法付诸实践，以确定有向图是否可以形成欧拉回路。它通过验证两个条件来完成此操作：

强连通性 (isSC)：它确定网络中每个度大于零的顶点是否强连通，表明每个顶点都可以从其他每个顶点访问。

入度和出度相等：它检查每个顶点的入度和出度是否相等，这是欧拉回路的一个基本要求。

该技术使用深度优先搜索 (DFS) 遍历图，验证所有顶点都已被访问。为了验证双向连接，图也以反向方式构建。最后一步，它利用图结构来确定给定的字符串集合是否可以连接在一起形成欧拉回路。

算法

步骤 1：声明一个名为 StringChainedCycle 的类来表示一个无向图。

步骤 2：使用以下值初始化类变量：“in”表示一个用于存储每个顶点入度的数组；“ver”表示顶点的总数；“adj”表示一个用于存储图结构的邻接列表的动态数组。

步骤 3：设置每个顶点的邻接列表和类变量。

步骤 4：更新入度中的目标顶点，并在图中添加连接两个顶点的边。

步骤 5：检查每个顶点的度数和连接情况，以确定网络是否具有欧拉回路。

步骤 6：使用深度优先搜索 (DFS) 确认非零度顶点之间存在强连通性。

步骤 7：开始深度优先搜索遍历，从指定顶点开始。

步骤 8：为了验证连接，获取图的转置（反向）。

步骤 9：以字符串数组为基础，创建一个图，其中每个字符串代表一条边。

步骤 10：如果图包含欧拉回路，则返回 true 表示字符串可以连接在一起。

实施

文件名：StringChainedCycle.java

import java.io.*;
import java.util.ArrayList;
import java.util.List;
// A class that operates as an undirected graph representation
public class StringChainedCycle
{
    static final int ch = 26;
    // total number of vertices
    int Ver; 
    // declaring a dynamic array of adjacency lists
    List<List<Integer>> adj; 
    int[] in;
    // with the use of Constructor
    StringChainedCycle(int Ver)
    {
    	this.Ver = Ver;
    	in = new int[Ver];
    	adj = new ArrayList<>(ch);
    	for(int i = 0; i < ch; i++)
    	{
    	    adj.add(i, new ArrayList<>());
    	}
    }
    // Function for adding an edge to graph
    void additionEdge(int vertex, int edge)
    {
    	adj.get(vertex).add(edge);
    	in[edge]++;
    }
    // A method to determine whether the graph is Eulerian or not 
    boolean CheckEulerianCycle() 
    {
    	// Verify that every vertex with a degree 
    	// other than zero is connected.
    	if (!VertexConnected())
    		return false;
    	// Verify that each vertex's in and 
    	// out degrees are the same.
    	for(int i = 0; i < Ver; i++)
    	if (adj.get(i).size() != in[i])
    		return false;
    	return true;
    }
    // If there is strong connectivity among all 
    // the non-zero degree vertices in the network, 
    // then this function returns true. 
    boolean VertexConnected() 
    {
    	// Identify every vertex as not having 
    	// been visited (for the first DFS).
    	boolean[] visit = new boolean[Ver];
    	for(int i = 0; i < Ver; i++)
    	visit[i] = false;
    	// Determine which vertex has a 
    	// degree that is not zero.
    	int N;
    	for(N = 0; N < Ver; N++)
    	if (adj.get(N).size() > 0)
    		break;
    	// Start the DFS traversal at the 
    	// first non-zero degree vertex.
    	DFS(N, visit);
    	// Return false if the DFS traversal
    	// doesn't visit every vertex.
    	for(int i = 0; i < Ver; i++)
    	if (adj.get(i).size() > 0 && !visit[i])
    		return false;
    	// Create a reversed graph
    	StringChainedCycle revgr = getTranspose();
        // Identify every vertex as not having 
        // been visited (for the second DFS).
    	for(int i = 0; i < Ver; i++)
    	visit[i] = false;
    	// Perform DFS on a reversed graph, beginning 
    	// at the first vertex. Beginning Vertex 
    	// must be identical to the first DFS's starting point.
    	revgr.DFS(N, visit);
    	// Return false if none of the vertices 
    	// in the second DFS are visited.
    	for(int i = 0; i < Ver; i++)
    	if (adj.get(i).size() > 0 && !visit[i])
    		return false;
    	return true;
    }
    // Function to perform DFS from the vertex.
    // Used in isConnected(); a recursive procedure 
    // for DFS that begins at the vertex
    void DFS(int vertex, boolean[] visit)
    {
    	// Identify the visited node as 
    	// the current one and print it.
    	visit[vertex] = true;
    	// Repeat for each vertex that is next to this vertex.
    	for(Integer i : adj.get(vertex))
    	if (!visit[i])
    	{
    		DFS(i, visit);
    	}
    }
    // Function that returns this 
    // graph's transposition,
    // or reverse It takes this function 
    // to use vertexConnected().
    StringChainedCycle getTranspose()
    {
    	StringChainedCycle g = new StringChainedCycle(Ver);
    	for(int vertex = 0; vertex < Ver; vertex++)
    	{
        	// Repeat for each vertex that
        	// is next to this vertex.
        	for(Integer i : adj.get(vertex))
        	{
        		g.adj.get(i).add(vertex);
        		g.in[vertex]++;
        	}
    	}
    	return g;
    }
    // This function accepts an array of 
    // strings as input and returns true 
    // if the array of strings can be linked
    // together to create a cycle.
    static boolean ChainedCycle(String[] arr, int N)
    {
        // creating a graph
    	StringChainedCycle gra = new StringChainedCycle(ch);
    	// Create an edge for each string starting 
    	// at the first and ending at the final character.
    	for(int i = 0; i < N; i++)
    	{
        	String str = arr[i];
        	gra.additionEdge(str.charAt(0) - 'a', str.charAt(str.length() - 1) - 'a');
    	}
    	// If an Eulerian cycle exists in the generated graph, 
    	//The given set of strings can be chained.
    	return gra.CheckEulerianCycle();
    }
    public static void main(String[] args) throws Exception
    {
    	String[] arr = { "bac", "cda", "aaa", "aab" };
    	int N = arr.length;
    	System.out.println((ChainedCycle(arr, N) ?
    					"Yes, it can be chained " : "No, it cannot be chained "));
    }
}

输出

Yes, it can be chained

复杂度分析

上述代码的时间复杂度为 O(N)，空间复杂度为 O(N)。

下一个主题用Java查找N的最大因子，使得NF小于K

← 上一个下一个 →

检查是否可以通过字符串数组链形成一个环（Java）

方法：使用有向图

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

检查是否可以通过字符串数组链形成一个环（Java）

方法：使用有向图

实施

相关帖子

Java 中的 FloatBuffer equals() 方法及示例

Java 中的旋转给定矩阵

Java Program to Find the Minimal Average of Any Slice Containing at Least Two Elements

Java Versions

Friends Pairing Problem in Java

Java short Keyword

Java 中 Object 转 int

Java 中的三个字符串的 LCS

Java 中的 Arrays.sort()

Dynamic Array in Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器