O(n) 时间复杂度和 O(1) space 复杂度的方法来查看两个字符串是否是彼此的排列

Question

是否有一种算法可以判断两个字符串是否是 O(n) 时间复杂度和 O(1) space 复杂度的相互排列？

Answer 1

这是我在 java 中编写的一个简单程序，它在 O(n) 中给出时间复杂度的答案，在 O(1) 中给出 space 复杂度的答案。它的工作原理是将每个字符映射到一个质数，然后将字符串的质数映射中的所有字符相乘。如果这两个字符串是排列组合，那么它们应该具有相同的唯一字符，每个字符出现的次数相同。

下面是完成此操作的一些示例代码：

// 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;

 }

Answer 2

是的，当然有一个非常好的方法。您必须为此使用计数排序。根本没有理由生成素数。这是描述该算法的 C 代码片段：

bool is_permutation(string s1, string s2) {
    if(s1.length() != s2.length()) return false;

    int count[256]; //assuming each character fits in one byte, also the authors sample solution seems to have this boundary
    for(int i=0;i<256;i++) count[i]=0;
    for(int i=0;i<s1.length();i++) { //count the digits to see if each digits occur same number of times in both strings
        count[ s1[i] ]++; 
        count[ s2[i] ]--;
    }

    for(int i=0;i<256;i++) { //see if there is any digit that appeared in different frequency
        if(count[i]!=0) return false;
    }
    return true;
}

编辑：（我决定在一些与我的程序顺序相关的评论之后添加这个）

让我们尝试计算我在程序中使用的算法的时间复杂度：

n = max len of strings
m = max allowed different characters, assuming will having all consecutive ascii value in range [0,m-1]
Time complexity: O(max(n,m)) 
Memory Complexity O(m)

现在假设 m 是一个常数，阶数变为

Time complexity: O(n) 
Memory Complexity O(1)

O(n) 时间复杂度和 O(1) space 复杂度的方法来查看两个字符串是否是彼此的排列

O(n) time complexity and O(1) space complexity way to see if two strings are permutations of each other

string

performance

big-o