Проверка того, являются ли две строки перестановками друг друга
Как определить, являются ли две строки перестановками друг друга
Ответы
Ответ 1
- Сортировка двух строковых символов.
- Сравните результаты, чтобы узнать, идентичны ли они.
Edit:
Вышеуказанный метод достаточно эффективен - O (n * log (n)), и, как показали другие, очень легко реализовать с использованием стандартного Java API. Еще более эффективная (но и большая работа) будет подсчет и сравнение появления каждого символа с использованием значения char в качестве индекса в массив счетчиков.
Я не знаю, есть ли эффективный способ сделать это рекурсивно. Неэффективный способ (O (n ^ 2), хуже, если он выполняется прямо):
- Если обе строки состоят из одного одинакового символа, верните true
- В противном случае:
- удалить один символ из первой строки
- Просмотр второй строки для появления этого символа
- Если нет, верните false
- В противном случае удалите указанный символ и рекурсивно применяйте алгоритм к остаткам обеих строк.
Ответ 2
Вставить @Michael Borgwardt слова в код:
public boolean checkAnagram(String str1, String str2) {
if (str1.length() != str2.length())
return false;
char[] a = str1.toCharArray();
char[] b = str2.toCharArray();
Arrays.sort(a);
Arrays.sort(b);
return Arrays.equals(a, b);
}
Ответ 3
Создайте Hashmap с символами первой строки в виде ключей и количеством событий в качестве значения; затем пройдите через вторую строку и для каждого символа найдите таблицу хэша и уменьшите число, если оно больше нуля. Если вы не найдете запись или если она уже равна 0, строки не являются перестановкой друг друга. Очевидно, что строка должна иметь одинаковую длину.
Ответ 4
Решение линейного времени в HashMap. Поверните и поместите первую строку в HashMap, сохраните счет каждого символа. Поверните вторую строку и, если она уже находится в hashmap, уменьшите счет на 1. В конце, если все символы были в строке, значение в hashmap будет равно 0 для каждого символа.
public class StringPermutationofEachOther {
public static void main(String[] args)
{
String s1= "abc";
String s2 ="bbb";
System.out.println(perm(s1,s2));
}
public static boolean perm(String s1, String s2)
{ HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int count =1;
if(s1.length()!=s2.length())
{
return false;
}
for(Character c: s1.toCharArray())
{
if(!map.containsKey(c))
map.put(c, count);
else
map.put(c, count+1);
}
for(Character c: s2.toCharArray())
{
if(!map.containsKey(c))
return false;
else
map.put(c, count-1);
}
for(Character c: map.keySet())
{
if(map.get(c)!=0)
return false;
}
return true;
}
}
Ответ 5
Вы можете попытаться использовать XOR, если одна строка является проницательностью другой, они должны иметь по существу одинаковые символы. Единственное отличие - это просто порядок символов. Поэтому использование трюка XOR поможет вам избавиться от порядка и сосредоточиться только на символах.
public static boolean isPermutation(String s1, String s2){
if (s1.length() != s2.length()) return false;
int checker = 0;
for(int i = 0; i < s1.length();i++ ){
checker ^= s1.charAt(i) ^ s2.charAt(i);
}
return checker == 0;
}
Ответ 6
- Сортируйте 2 строки по символам и сравните, если они одинаковы (O (n log n), O (n) пробел) или
- Настройте частоту символов двух строк и сравните, если они одинаковы (время O (n), O (n)).
Ответ 7
Вы можете взглянуть на String.toCharArray и Массивы .sort
Ответ 8
Сначала вы проверяете длины (n), если они не одинаковы, они не могут быть перестановками друг друга. Теперь создайте два HashMap<Character, Integer>. Итерации по каждой строке и укажите количество раз, когда каждый символ встречается в строке. Например. если строка aaaaa, на карте будет только один элемент с ключом a и значением 5. Теперь проверьте, идентичны ли две карты. Это алгоритм O(n).
EDIT с фрагментом кода:
boolean checkPermutation(String str1, String str2) {
char[] chars1 = str1.toCharArray();
char[] chars2 = str2.toCharArray();
Map<Character, Integer> map1 = new HashMap<Character, Integer>();
Map<Character, Integer> map2 = new HashMap<Character, Integer>();
for (char c : chars1) {
int occ = 1;
if (map1.containsKey(c) {
occ = map1.get(c);
occ++;
}
map1.put(c, occ);
}
// now do the same for chars2 and map2
if (map1.size() != map2.size()) {
return false;
}
for (char c : map1.keySet()) {
if (!map2.containsKey(c) || map1.get(c) != map2.get(c)) {
return false;
}
}
return true;
}
Ответ 9
Я сделал это, и он работает хорошо и быстро:
public static boolean isPermutation(String str1, String str2)
{
char[] x = str1.toCharArray();
char[] y = str2.toCharArray();
Arrays.sort(x);
Arrays.sort(y);
if(Arrays.equals(x, y))
return true;
return false;
}
Ответ 10
public boolean isPermutationOfOther(String str, String other){
if(str == null || other == null)
return false;
if(str.length() != other.length())
return false;
Map<Character, Integer> characterCount = new HashMap<Character, Integer>();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
int count = 1;
if(characterCount.containsKey(c)){
int k = characterCount.get(c);
count = count+k;
}
characterCount.put(c, count);
}
for (int i = 0; i < other.length(); i++) {
char c = other.charAt(i);
if(!characterCount.containsKey(c)){
return false;
}
int count = characterCount.get(c);
if(count == 1){
characterCount.remove(c);
}else{
characterCount.put(c, --count);
}
}
return characterCount.isEmpty();
}
Ответ 11
Изменение на других подходах, но в этом используется 2 массива int для отслеживания символов, сортировки, и вам нужно всего лишь сделать 1 для цикла по строкам. Цикл for, который я делаю по массивам int для проверки перестановки, является константой, поэтому не является частью N.
Память постоянна.
O (N) время выполнения.
// run time N, no sorting, assume 256 ASCII char set
public static boolean isPermutation(String v1, String v2) {
int length1 = v1.length();
int length2 = v2.length();
if (length1 != length2)
return false;
int s1[] = new int[256];
int s2[] = new int[256];
for (int i = 0; i < length1; ++i) {
int charValue1 = v1.charAt(i);
int charValue2 = v2.charAt(i);
++s1[charValue1];
++s2[charValue2];
}
for (int i = 0; i < s1.length; ++i) {
if (s1[i] != s2[i])
return false;
}
return true;
}
}
Тестирование устройств
@Test
public void testIsPermutation_Not() {
assertFalse(Question3.isPermutation("abc", "bbb"));
}
@Test
public void testIsPermutation_Yes() {
assertTrue(Question3.isPermutation("abc", "cba"));
assertTrue(Question3.isPermutation("abcabcabcabc", "cbacbacbacba"));
}
Ответ 12
Я работаю над библиотекой Java, которая должна упростить вашу задачу. Вы можете повторно реализовать этот алгоритм, используя только два вызова метода:
boolean arePermutationsOfSameString(String s1, String s2) {
s1 = $(s1).sort().join();
s2 = $(s2).sort().join();
return s1.equals(s2);
}
TestCase
@Test
public void stringPermutationCheck() {
// true cases
assertThat(arePermutationsOfSameString("abc", "acb"), is(true));
assertThat(arePermutationsOfSameString("bac", "bca"), is(true));
assertThat(arePermutationsOfSameString("cab", "cba"), is(true));
// false cases
assertThat(arePermutationsOfSameString("cab", "acba"), is(false));
assertThat(arePermutationsOfSameString("cab", "acbb"), is(false));
// corner cases
assertThat(arePermutationsOfSameString("", ""), is(true));
assertThat(arePermutationsOfSameString("", null), is(true));
assertThat(arePermutationsOfSameString(null, ""), is(true));
assertThat(arePermutationsOfSameString(null, null), is(true));
}
PS
В случае, если вы можете клонировать souces в bitbucket.
Ответ 13
Обязательный Guava однострочный:
boolean isAnagram(String s1, String s2) {
return ImmutableMultiset.copyOf(Chars.asList(s1.toCharArray())).equals(ImmutableMultiset.copyOf(Chars.asList(s2.toCharArray())));
}
(Просто для удовольствия. Я не рекомендую отправлять это для вашего задания.)
Ответ 14
Как вы просили, вот полное решение, использующее рекурсию.
Теперь все, что вам нужно сделать, это:
- Выясните, на каком языке это
- Перевести его на Java.
Удачи: -)
proc isAnagram(s1, s2);
return {s1, s2} = {''} or
(s2 /= '' and
(exists c = s1(i) |
s2(1) = c and
isAnagram(s1(1..i-1) + s1(i+1..), s2(2..))));
end isAnagram;
Ответ 15
Я сделал это с помощью С#
bool Arepermutations(string string1, string string2)
{
char[] str1 = string1.ToCharArray();
char[] str2 = string2.ToCharArray();
if (str1.Length !=str2.Length)
return false;
Array.Sort(str1);
Array.Sort(str2);
if (str1.Where((t, i) => t!= str2[i]).Any())
{
return false;
}
return true;
}
Ответ 16
public boolean permitation(String s,String t){
if(s.length() != t.length()){
return false;
}
int[] letters = new int[256];//Assumes that the character set is ASCII
char[] s_array = s.toCharArray();
for(char c:s_array){ /////count number of each char in s
letters[c]++;
}
for(int i=0;i<t.length();i++){
int c = (int)t.charAt(i);
if(--letters[c]<0){
return false;
}
}
return true;
}
Ответ 17
import java.io.*;
public class permute
{
public static String sort(String s)
{
char[] str = s.toCharArray();
java.util.Arrays.sort(str);
return new String(str);
}
public static boolean permutation(String s,String t)
{
if(s.length()!=t.length())
{
return false;
}
return sort(s).equals(sort(t));
}
public static void main(String[] args) throws IOException
{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String string = null;
boolean x=true;
System.out.println("Input String:");
string = bf.readLine();
System.out.println("Input another String:");
String result = bf.readLine();
String resultant = sort(string);
if(x==permutation(result,resultant))
{
System.out.println("String"+" "+"("+result+")"+"is a permutation of String"+" "+"("+string+")");
}
else
{
System.out.println("Sorry No anagram found");
}
}
}
Ответ 18
public class TwoStrgPermutation {
public int checkForUnique(String s1, String s2)
{
int[] array1 = new int[256];
int[] array2 = new int[256];
array1 = arrayStringCounter(array1,s1);
array2 = arrayStringCounter(array2,s2);
if(Arrays.equals(array1, array2))
return 0;
else
return 1;
}
public int[] arrayStringCounter(int[] array,String s)
{
int val;
for(int i=0;i<s.length();i++)
{
val = (int)s.charAt(i);
array[val]++;
}
return array;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
InputStreamReader in = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(in);
TwoStrgPermutation obj = new TwoStrgPermutation();
try {
String string1 = br.readLine();
String string2 = br.readLine();
int len1 = string1.length();
int len2 = string2.length();
if(len1==len2)
{
int result = obj.checkForUnique(string1,string2);
if (result == 0){
System.out.println("yes it is a permutation");
}
else if (result >0)
{
System.out.println("no it is not");
}
}
else
{
System.out.println("no it is not");
}
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
Ответ 19
>>>def isPermutation = lambda x, y: set([i for i in x]) == set([j for j in x])
>>>isPermutation("rasp", "spar")
>>>True
Ответ 20
Это решение O (N), в котором N - длина более короткой строки.
Недостаток заключается в том, что допустимы только символы ASCII.
Если мы хотим улучшить применимость, мы можем заменить хеш-таблицу для int charNums[].
Но это также означает, что C не будет хорошим выбором, поскольку нет стандартной реализации хеш-таблицы для C.
int is_permutation(char *s1, char *s2)
{
if ((NULL == s1) ||
(NULL == s2)) {
return false;
}
int static const
_capacity = 256; // Assumption
int
charNums[_capacity] = {0};
char
*cRef1 = s1,
*cRef2 = s2;
while ('\0' != *cRef1 && '\0' != *cRef2) {
charNums[*cRef1] += 1;
charNums[*cRef2] -= 1;
cRef1++;
cRef2++;
}
if ('\0' != *cRef1 || '\0' != *cRef2) {
return false;
}
for (int i = 0; i < _capacity; i++) {
if (0 != charNums[i]) {
return false;
}
}
return true;
}
Ответ 21
Создайте два метода:
1. Первый метод принимает строку и возвращает отсортированную строку:
public String sort(String str) {
char char_set[] = str.toCharArray();
Arrays.sort(char_set);
return new String(char_set);
}
2. Второй метод принимает две строки и возвращает логическое значение:
`public boolean sort(String x, String y) {
if (x.length() != y.length()) {
System.out.println("false");
return false;
}
System.out.println(sort(x).equals(sort(y)));
return sort(x).equals(sort(y));
}`
Ответ 22
Это можно сделать, используя словарь в С#. Основная реализация такова:
private static bool IsPermutation(string str1, string str2)
{
if (str1.Length != str2.Length)
return false;
var dictionary = new Dictionary<char, int>();
foreach(var x in str1)
{
if (dictionary.ContainsKey(x))
dictionary[x] += 1;
else
dictionary.Add(x, 1);
}
foreach (var y in str2)
{
if (dictionary.ContainsKey(y))
{
if (dictionary[y] > 0)
dictionary[y] -= 1;
else
return false;
}
else
return false;
}
foreach(var el in dictionary)
{
if (el.Value != 0)
return false;
}
return true;
}
Сложность времени - это O (n), линейное решение.
Ответ 23
public static boolean isPermutation(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}else if(s1.length()==0 ){
return true;
}
else if(s1.length()==1){
return s1.equals(s2);
}
char[] s = s1.toCharArray();
char[] t = s2.toCharArray();
for (int i = 0; i < s.length; i++) {
for (int j = 0; j < t.length; j++) {
if (s.length == s1.length() && (i == 0 && j == t.length - 1) && s[i] != t[j]) {
return false;
}
if (s[i] == t[j]) {
String ss = new String(s);
String tt = new String(t);
s = (ss.substring(0, i) + ss.substring(i + 1, s.length)).toCharArray();
t = (tt.substring(0, j) + tt.substring(j + 1, t.length)).toCharArray();
System.out.println(new String(s));
System.out.println(new String(t));
i = 0;
j = 0;
}
}
}
return s[0]==t[0] ;
}
Это решение работает для любой кодировки. С сложностью O (n).
Выход для: isPermutation("The Big Bang Theory", "B B T Tehgiangyroeh")
he Big Bang Theory
B B Tehgiangyroeh
e Big Bang Theory
B B Tegiangyroeh
Big Bang Theory
B B Tgiangyroeh
Big Bang Theory
BB Tgiangyroeh
ig Bang Theory
B Tgiangyroeh
g Bang Theory
B Tgangyroeh
Bang Theory
B Tangyroeh
Bang Theory
B Tangyroeh
Bng Theory
B Tngyroeh
Bg Theory
B Tgyroeh
B Theory
B Tyroeh
BTheory
BTyroeh
Bheory
Byroeh
Beory
Byroe
Bory
Byro
Bry
Byr
By
By
B
B
true
Ответ 24
Лучший способ сделать это - сначала отсортировать две строки, а затем сравнить их. Это не самый эффективный способ, но он чист и связан с временем выполнения процедуры сортировки.
boolean arePermutation(String s1, String s2) {
if(s1.lenght() != s2.lenght()) {
return false;
}
return mySort(s1).equals(mySort(s2));
}
String mySort(String s) {
Char letters[] = s.toCharArray();
Arrays.sort(letters);
return new String(letters);
}
Ответ 25
String str= "abcd";
String str1 ="dcazb";
int count=0;
char s[]= str.toCharArray();
char s1[]= str1.toCharArray();
for(char c:s)
{
count = count+(int)c ;
}
for(char c1:s1)
{
count=count-(int)c1;
}
if(count==0)
System.out.println("String are Anagram");
else
System.out.println("String are not Anagram");
}
Ответ 26
Вот простая программа, которую я написал, которая дает ответ в O (n) для временной сложности и O (1) для космической сложности. Он работает путем сопоставления каждого символа с простым числом и последующего умножения вместе всех символов в строковых первичных сопоставлениях. Если две строки являются перестановками, то они должны иметь одинаковые уникальные символы с одинаковым количеством вхождений.
Вот пример кода, который выполняет следующее:
// maps keys to a corresponding unique prime
static Map<Integer, Integer> primes = generatePrimes(255); // use 255 for
// ASCII or the
// number of
// possible
// characters
public static boolean permutations(String s1, String s2) {
// both strings must be same length
if (s1.length() != s2.length())
return false;
// the corresponding primes for every char in both strings are multiplied together
int s1Product = 1;
int s2Product = 1;
for (char c : s1.toCharArray())
s1Product *= primes.get((int) c);
for (char c : s2.toCharArray())
s2Product *= primes.get((int) c);
return s1Product == s2Product;
}
private static Map<Integer, Integer> generatePrimes(int n) {
Map<Integer, Integer> primes = new HashMap<Integer, Integer>();
primes.put(0, 2);
for (int i = 2; primes.size() < n; i++) {
boolean divisible = false;
for (int v : primes.values()) {
if (i % v == 0) {
divisible = true;
break;
}
}
if (!divisible) {
primes.put(primes.size(), i);
System.out.println(i + " ");
}
}
return primes;
}
Ответ 27
Основываясь на комментарии к этому решению, fooobar.com/questions/391050/..., этот подход, пересмотренный.
private static boolean is_permutation(String s1, String s2) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int count = 1;
if(s1.length()!=s2.length()) {
return false;
}
for(Character c: s1.toCharArray()) {
if(!map.containsKey(c)) {
map.put(c, 1);
}
else {
map.put(c, map.get(c) + 1);
}
}
for(Character c: s2.toCharArray()) {
if(!map.containsKey(c)) {
return false;
}
else {
map.put(c, map.get(c) - 1);
}
}
for(Character c: map.keySet()) {
if(map.get(c) != 0) { return false; }
}
return true;
}
Ответ 28
bool is_permutation1(string str1, string str2) {
sort(str1.begin(), str1.end());
sort(str2.begin(), str2.end());
for (int i = 0; i < str1.length(); i++) {
if (str1[i] != str2[i]) {
return false;
}
}
return true;
}
Ответ 29
Я сделал это на C, если кто-то заботится. Он принимает значения ASCII и использует порядковое значение символов:
bool is_permutation(const char *a, const char *b)
{
if (a == NULL || b == NULL)
return false;
if (strlen(a) != strlen(b))
return false;
int sum_a = 0, sum_b = 0;
while (*a != '\0')
sum_a += (int)*a++;
while (*b != '\0')
sum_b += (int)*b++;
return (sum_a == sum_b);
}
