Как найти минимальное количество операций

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

#include <iostream>

#include <unordered_set>

#include <string>

using namespace std;

// Функция для нахождения минимального количества операций, необходимых для преобразования данного

// строка в другую строку

int getMinimumOperations(string first, string second)

{

    // для отслеживания минимального количества необходимых операций

    int count = 0;

    // `i` и `j` отслеживают текущий индекс символов в

    // первая и вторая строки соответственно

    // начинаем с конца первой и второй строки

    for (int i = first.length() — 1, j = i; i >= 0; i—, j—)

    {

        // если текущий символ обеих строк не совпадает,

        // ищем `second[j]` в подстроке `first[0, i-1]` и

        // увеличиваем счетчик для каждого хода

        while (i >= 0 && first[i] != second[j])

        {

            i—;

            count++;

        }

    }

    // вернуть минимальное количество требуемых операций

    return count;

}

// Функция для определения, может ли первая строка быть преобразована в

// вторая строка

bool isTransformable(string first, string second)

{

    // если длина обеих строк отличается

    if (first.length() != second.length()) {

        return false;

    }

    // строим multiset из символов первой и второй строки

    // (используется multiset, так как оно допускает дублирование)

    unordered_multiset<char> chars1(first.begin(), first.end());

    unordered_multiset<char> chars2(second.begin(), second.end());

    // вернуть true, если обе строки имеют одинаковый набор символов

    return (chars1 == chars2);

}

int main()

{

    string first = «ADCB»;

    string second = «ABCD»;

    if (isTransformable(first, second))

    {

        cout << «The minimum operations required to convert the string «

             << first << » to string « << second << » are «

             << getMinimumOperations(first, second);

    }

    else {

        cout << «The string cannot be transformed»;

    }

    return 0;

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

import java.util.Map;

import java.util.function.Function;

import java.util.stream.Collectors;

class Main

{

    // Функция для нахождения минимального количества операций, необходимых для преобразования данного

    // строка в другую строку

    public static int getMinimumOperations(String first, String second)

    {

        // для отслеживания минимального количества необходимых операций

        int count = 0;

        // `i` и `j` отслеживают текущий индекс символов в

        // первая и вторая строки соответственно

        // начинаем с конца первой и второй строки

        for (int i = first.length() — 1, j = i; i >= 0; i—, j—)

        {

            // если текущий символ обеих строк не совпадает,

            // ищем `second[j]` в подстроке `first[0, i-1]` и

            // увеличиваем счетчик для каждого хода

            while (i >= 0 && first.charAt(i) != second.charAt(j))

            {

                i—;

                count++;

            }

        }

        // вернуть минимальное количество требуемых операций

        return count;

    }

    // Функция для определения, может ли первая строка быть преобразована в

    // вторая строка

    public static boolean isTransformable(char[] first, char[] second)

    {

        // базовый вариант

        if (first == null || second == null) {

            return false;

        }

        // если длина обеих строк отличается

        if (first.length != second.length) {

            return false;

        }

        // вернуть true, если обе строки имеют одинаковый набор символов

        return getFrequencyMap(first).equals(getFrequencyMap(second));

    }

    // Вспомогательная функция для создания карты частот

    public static Map<Character, Long> getFrequencyMap(char[] chars)

    {

        return new String(chars).chars().mapToObj(ch -> (char) ch)

                .collect(Collectors.groupingBy(Function.identity(),

                    Collectors.counting()));

    }

    public static void main(String[] args)

    {

        String first = «ADCB»;

        String second = «ABCD»;

        if (isTransformable(first.toCharArray(), second.toCharArray()))

        {

            System.out.println(«The minimum operations required to convert the string «

                    + first + » to string « + second + » are «

                    + getMinimumOperations(first, second));

        }

        else {

            System.out.println(«The string cannot be transformed»);

        }

    }

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

import collections

# Функция для нахождения минимального количества операций, необходимых для преобразования данного

# в другую строку

def getMinimumOperations(first, second):

    # для отслеживания минимального количества необходимых операций

    count = 0

    # `i` и `j` отслеживают индекс текущего символа в

    # первая и вторая строки соответственно

    # начинаются с конца первой и второй строки

    i = len(first) — 1

    j = i

    while i >= 0:

        #, если текущий символ обеих строк не совпадает,

        # ищет `second[j]` в подстроке `first[0,i-1]` и

        # увеличивает счет для каждого хода

        while i >= 0 and first[i] != second[j]:

            i = i — 1

            count = count + 1

        i = i — 1

        j = j — 1

    # возвращает минимально необходимые операции

    return count

# Функция для определения возможности преобразования первой строки в

# вторая строка

def isTransformable(first, second):

    #, если длина обеих строк отличается

    if len(first) != len(second):

        return False

    # возвращает true, если обе строки имеют одинаковый набор символов.

    return collections.Counter(first) == collections.Counter(second)

if __name__ == ‘__main__’:

    first = ‘ADCB’

    second = ‘ABCD’

    if isTransformable(list(first), list(second)):

        print(‘The minimum operations required to convert the String’, first,

              ‘to string’, second, ‘are’, getMinimumOperations(first, second))

    else:

        print(‘The string cannot be transformed’)