Java Program to Check if Two Strings are Cyclic Permutations of Each Other

2025 年 3 月 28 日 | 阅读 4 分钟

这是通常会在Google、Microsoft、TCS、Accenture等著名 IT 公司面试中遇到的问题。通过弄清楚解决方案，可以评估面试者的逻辑推理、批判性思维和解决问题的能力。在本节中，我们将创建一个 Java 程序，使用不同的方法检查两个相同长度的字符串是否是彼此的循环排列。

循环排列

当一个字符串可以通过旋转其字符变成另一个字符串时，就会发生循环排列。

示例

String str1 = "ABCD";
String str2 = "CDAB";

输出

是（因为旋转“CDAB”得到“ABCD”）

有多种方法可以检查两个字符串是否是彼此的循环排列。在本节中，我们将讨论以下方法

排序和比较方法
计数和比较方法
单数组计数方法

使用排序和比较方法

排序和比较是一种方法，其中两个字符串首先被转换为字符数组，然后进行排序和比较。如果排序后的数组匹配，则认为字符串是彼此的排列。

让我们在 Java 程序中实现上述方法。

文件名：PermutationChecker.java

import java.util.*;  // Importing the utility package for Arrays methods like sort
class PermutationChecker {
    static boolean arePermutations(String firstString, String secondString) { 
        // Get the length of the first string
        int length1 = firstString.length(); 
        // Get the length of the second string
        int length2 = secondString.length(); 
        // If the lengths are not equal, they cannot be permutations
        if (length1 != length2) 
            return false; 
        // Convert the first string to a character array
        char[] charArray1 = firstString.toCharArray();
        // Convert the second string to a character array
        char[] charArray2 = secondString.toCharArray();
        // Sort both character arrays
        Arrays.sort(charArray1); 
        Arrays.sort(charArray2); 
        // Compare each character of the sorted arrays
        for (int i = 0; i < length1; i++) 
            // If any characters don't match, they are not permutations
            if (charArray1[i] != charArray2[i]) 
                return false; 
        // If all characters match, they are permutations
        return true; 
    } 
    public static void main(String[] args) { 
        // Input strings to check if they are permutations
        String firstString = "test"; 
        String secondString = "ttew"; 
        // Call the arePermutations method and print the result
        if (arePermutations(firstString, secondString)) 
            System.out.println("Yes"); // If they are permutations, print "Yes"
        else
            System.out.println("No");  // If not, print "No"
    }
}   

输出

No

时间复杂度： O(n log n)

辅助空间： O(n)

使用计数和比较方法

计数和比较是一种方法，其中使用数组计算两个字符串中的字符频率。然后比较这些频率数组以确定字符串是否是彼此的排列。

让我们在 Java 程序中实现上述方法。

文件名：PermutationChecker.java

import java.io.*;  // Import necessary classes for input/output operations
import java.util.*;  // Import utility classes such as Arrays
class PermutationChecker {
	static int CHAR_COUNT = 256;  // Number of possible character values (ASCII)
	//Method to check if two character arrays are permutations of each other
	static boolean arePermutations(char[] firstString, char[] secondString) {
		// Create and initialize count arrays for both strings
		int[] countFirst = new int[CHAR_COUNT];
		Arrays.fill(countFirst, 0);  // Fill countFirst array with zeros
		int[] countSecond = new int[CHAR_COUNT];
		Arrays.fill(countSecond, 0);  // Fill countSecond array with zeros
		int i;
		// Increment the count of each character in the respective arrays
		for (i = 0; i < firstString.length && i < secondString.length; i++) {
		countFirst[firstString[i]]++;  // Increment count for firstString character
	countSecond[secondString[i]]++;  // Increment count for secondString character
		}
		// Check if the lengths of the two strings are different
		if (firstString.length != secondString.length)
			return false;  // If lengths differ, they can't be permutations
		// Compare the count arrays
		for (i = 0; i < CHAR_COUNT; i++)
			if (countFirst[i] != countSecond[i])
				return false;  // If counts differ, they are not permutations
		return true;  // If all counts match, the strings are permutations
	}
	// Main Method to test the permutation checking
	public static void main(String[] args) {
		// Define and convert strings to character arrays
		char[] firstString = ("javatpoint").toCharArray();
		char[] secondString = ("pointjavat").toCharArray();
		// Check if the character arrays are permutations and print the result
		if (arePermutations(firstString, secondString))
			System.out.println("Yes"); 
		else
			System.out.println("No");
	}
}   

输出

Yes

时间复杂度： O(n)，其中 n 是字符串的长度。

辅助空间： O(1)

使用单数组计数方法

该方法使用单个数组来跟踪两个字符串中字符的频率。通过检查处理后它们的字符计数是否匹配来确保字符串是排列。

文件名：PermutationChecker.java

import java.io.*;  // Import necessary classes for input/output operations
import java.util.*;  // Import utility classes such as Arrays
class PermutationChecker {
	static int CHAR_COUNT = 256;  // Number of possible character values (ASCII)
	static boolean arePermutations(char[] firstString, char[] secondString) {
		if (firstString.length != secondString.length) 
			return false;  
		int[] count = new int[CHAR_COUNT];  // Create a count array for character frequencies
		Arrays.fill(count, 0);  // Initialize the count array with zeros
		// Increment counts for characters in firstString and decrement for characters in secondString
		for (int i = 0; i < firstString.length; i++) {
			count[firstString[i]]++;  // Increment count for characters in firstString
			count[secondString[i]]--;  // Decrement count for characters in secondString
		}
		// Check if all values in the count array are zero
		for (int i = 0; i < CHAR_COUNT; i++) {
			if (count[i] != 0) 
			return false;  // If any count is not zero, strings are not permutations
		}
		return true;  // All counts are zero, strings are permutations
	}
	public static void main(String[] args) {
		// Define and convert strings to character arrays
		char[] firstString = ("javatpoint").toCharArray();
		char[] secondString = ("pointjavat").toCharArray();
		// Check if the character arrays are permutations and print the result
		if (arePermutations(firstString, secondString))
			System.out.println("Yes");  // Print "Yes" if they are permutations
		else
			System.out.println("No");  // Print "No" if they are not permutations
	}
}   

输出

Yes

下一个主题Java 中的 List 与 Set

Java Program to Check if Two Strings are Cyclic Permutations of Each Other

循环排列

使用排序和比较方法

使用计数和比较方法

使用单数组计数方法

联系信息

关注我们

教程

面试题

在线编译器

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 Program to Check if Two Strings are Cyclic Permutations of Each Other

循环排列

使用排序和比较方法

使用计数和比较方法

使用单数组计数方法

相关帖子

Java 变体

Java 中运算符的结合性

Java missing return statement

Build an Array with Stack Operations in Java

Java 中计算列表的平均值

Java 中获取日期范围

Java 中的矩阵对角线求和

Rotate Bits Problem in Java

Java 程序获取集合的大小并验证集合是否为空

Java String Max Size

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器