Можно ли преобразовать исходную строку в строку назначения? - PullRequest
Новая
       20

Можно ли преобразовать исходную строку в строку назначения?

0 голосов
/ 31 мая 2019

Существует ли последовательность шагов преобразования для преобразования данной исходной строки в строку назначения?

Примечание: на каждом шаге может быть преобразован один символ (замена должна быть символом между «A» - «Z»), и все вхождения этого символа должны быть преобразованы. Примеры приведены ниже. 

Source: "ABA" 
Dest: "BAB" 
Output: True 
Explanation: ABA -> A**C**A -> **B**C**B** -> B**A**B 

Source: "AA" 
Dest: "BC" 
Output: False 
Explanation: AA -> BB

Я думаю HashMap работает. Но есть ли другая структура данных, в которой я не собираюсь сравнивать символ за символом?

Ответы [ 3 ]

1 голос
/ 31 мая 2019

Вы можете попробовать это: 

private static boolean test(String s1, String s2) {

    if(s1.length() != s2.length()) return false;

    Map<Character, Character> map = new HashMap<>();

    for (int i = 0; i < s1.length(); i++) {
        char c1 = s1.charAt(i);
        char c2 = s2.charAt(i);

        if (map.containsKey(c1)) {
            if (!map.get(c1).equals(c2)) {
                return false;
            }
        } else {
            map.put(c1, c2);
        }
    }
    return map.size() < 26;
}
0 голосов
/ 01 июня 2019

Вы должны проверить, сколько символов повторяется в обеих строках.Пожалуйста, проверьте, работает ли приведенная ниже логика 

 1. Declare two arrays of size equal to the length of the string (suppose N). (The length 
    of both the strings must be equal first of all). This array stores the number of 
    characters which are repeated once,twice,thrice...N times

 2. Traverse the strings and calculate the frequency of each character. Sorting the 
    strings beforehand might help.

 3. On getting the frequency of one character in a particular string, update the array 
    corresponding to that string. 

 4. Set array[newly found frequency] += 1;

 5. Repeat steps 3-4 for both the strings. After this is done for both the strings, we 
    have two arrays containing the information about how many characters are repeated how 
    many times in both the strings.

 6. Next step is to match both the arrays. If they match return True else False.

Я объясню вышеупомянутые шаги на вашем примере: 

Source: ABA
Dest: BAB

Arrays would be: arr1[3]={0,0,0} and arr2[3]={0,0,0}

(storing nummber of characters with frequency n in arr[n-1])

In string 1: Characters with 2 repetitions: 1 (A) so- arr1[2-1]+=1; 
             Characters with 1 repetition: 1 (B)  so- arr1[1-1]+=1;

arr1= {1,1,0}

In string 2: Characters with 2 repetitions: 1 (B) so- arr2[2-1]+=1;
             Characters with 1 repetition: 1 (A)  so- arr2[1-1]+=1;

arr2= {1,1,0}

As arr1 and arr2 match, the strings are convertible.

Надеюсь, это поможет:)

0 голосов
/ 31 мая 2019

Должно возвращаться значение true, если обе строки должны иметь одинаковую длину и одинаковые символы (не совпадающие с теми, которые мы собираемся преобразовать). Количество совпадений.

Проверьте, работает ли приведенный ниже подход:

  1. проверьте, чтобы длина обеих строк была одинаковой.
  2. Получите счетчики всех символов строк источника и назначения.
  3. Сортируйте данные обоих счетчиков и итерируйте оба, верните false, если вынайти другой счет по одному и тому же индексу.
  4. Иначе верните true.
...