JS程序按指定幅度按指定方向旋转给定的字符串

Question

函数必须采用两个字符串参数：一个是要旋转的字符串，第二个字符串表示在特定方向上以特定幅度旋转的任意次数。第二个字符串的形式为： X a X b X c ....... 其中 X 表示旋转方向，可以是 L 或 R。 a,b,c... 是表示大小的整数(不超过9个)在他们左边的方向。

例如，如果这些是参数：("abcde","L 3 R 2 R 4") 输出将是 YES

解释：

此处，旋转数为3。
应用第一次旋转 L 3 后，字符串为： 'deabc'。这里，第一个字符是 'd'
应用第二次旋转 R 2 后，字符串为： 'bcdea'。这里，第一个字符是 'b'
应用第三次旋转 R 4 后，字符串为： 'cdeab'。这里，第一个字符是 'c'

因此，在所有旋转之后，FIRSTCHARSTRING 字符串将是 "dbc"，这是原始字符串 "abcde".

的子字符串的变位词

这是我尝试过但没有成功的方法


const task18 = (str1, str2) => {
  let count;
  for (let i in str2) {
    if (str2[i] === "L") {
      let ans = str1.substring(str2[i + 1]) + str1.substring(0, str2[i + 1]);
      count = ans[0];
      return ans;
    } else {
      return str1.substring(str1, str1.length - str2[i + 1]);
    }
  }
};

Answer 1

这里有一个解决方案，不修改中间的字符串，只是跟踪每次旋转后第一个字母的位置。

// After applying first rotation L 3, the string is: 'deabc'. Here, the first character is 'd'
// After applying second rotation R 2, the string is: 'bcdea'. Here, the first character is 'b'
// After applying third rotation R 4, the string is: 'cdeab'. Here, the first character is 'c'
// Thus, after all the rotations the FIRSTCHARSTRING string will be "dbc" which is an anagram of a sub string of original string "abcde".

// Check if the result is an anagram of a substring of the full string.
const isAnagram = (full, part) => {   
  let isPartAnagram = true;
  partAsArray = part.split("");
  for (let i in partAsArray) {
    let c = partAsArray[i];
    let pos = full.indexOf(c);
    // If the letter is not part anymore of the string, it's not an anagram.
    if (pos === -1) {
      isPartAnagram = false;
      return;
    }
    // Remove char from string.
    full = full.substring(0, pos) + full.substring(pos+1)
  }
  return isPartAnagram;
}

const task18 = (str1, str2) => {
  // Let's remove whitespace. We don't need that.
  str2 = str2.replace(/\s/g, "");
  
  let result = "";
  let currPos = 0;
  // mod is used to ensure that array boundaries are no problem
  let mod = str1.length;
  for (let i = 0; i < str2.length; i++) {
    if (str2[i] === "L") {
      currPos = (currPos + str2[++i]) % mod;
      // Add 'pseudofirst' letter to result.
      result += str1[currPos];
    } else {
      currPos = (mod + currPos - str2[++i]) % mod;
      // Add 'pseudofirst' letter to result.
      result += str1[currPos];
    }
  }
  
  let answer = isAnagram(str1, result) ? 'YES' : 'NO'
  console.log(str1, str2, result, answer);
  
  return answer;
}

task18("abcde","L 3 R 2 R 4");
task18("linkinpark", "L 6 R 5 L 4");
task18("carrace", "L 2 R 2 L 3") // should return NO
task18("pnesumonoultramicroscopicsilicovolcanoconiosisfloccinaucinihilipilification", "R9R1L4L9") // should return yes

Answer 2

几个问题：

你总是在第一次迭代时退出循环（return）。
substring 的最后一次调用将一个字符串作为第一个参数，而应该是一个数字。
count = ans[0]; 从错误的地方开始计数。将从 str2 检索，而不是 ans.
没有任何尝试查找字谜是否匹配
该函数尝试 return 部分 str1，但分配给 return "YES" 或 "NO".

最简单的部分是旋转。其实没必要真的旋转str1。仅用索引指向旋转后字符串的开头会更有效率。

困难的部分是找出构造的字符串是否是str1的子串的变位词。困难在于 str1 中的某些字符可能重复，因此当您 select 在重复的字母中输入错误的字符时，匹配尝试可能会失败。这可以通过使用递归和回溯尝试在重复项中使用一个字符，然后使用下一个字符来解决，直到成功或所有尝试都失败。

您可以采取一些额外措施来缩短运行时间：当旋转字符串的旋转次数多于 str1 中的字符数时，您已经可以 return "NO".

如果旋转产生的字符串使用某个字符的次数多于 str1 中出现的字符（因为通过旋转重新访问了某个字符位置），那么您也可以 return "NO".

对于递归的部分，可以先找str1中出现次数最少的字符，这样就不用多次重试了。您还可以跟踪匹配字符在 str1 中相距多远：如果它们相距太远（超过子字符串的总大小），则继续该方向没有用。

下面全部实现：

function task18(str, rotations) {
    // convert second argument: extract single rotations and convert to signed offsets
    rotations = rotations.replace(/R\s*/g, "-").match(/-?\d/g).map(Number);
    
    // Make a naive check to exclude rotation strings that are too long
    if (rotations.length > str.length) return "NO"; // too many characters will be selected

    // Register at which indexes a character occurs (as there may be duplicate characters)
    let occurrences = Object.fromEntries(Array.from(str, c => [c, []]));
    Array.from(str, (c, i) => occurrences[c].push(i)); 
    // Count characters in str so to be able to detect a "NO" sooner.
    let available = Object.fromEntries(Array.from(str, c => [c, occurrences[c].length]));

    // Don't actually rotate the string, but maintain a current index
    let current = 0;
    let result = []; // The selected characters
    for (let rot of rotations) {
        let c = str[current = (current + str.length + rot) % str.length];
        if (!available[c]--) return "NO"; // too many of the same character
        result.push(c);
    }

    // Reorder characters, so those which have the least available occurrences
    //  in the input string come first.
    // This will optimise the depth first search for an anagram.
    result.sort((a, b) => available[a] - available[b]);

    // Perform a depth-first search for an anagram match
    return (function dfs(i=0, first=str.length, last=-1) {
        // first/last are the extreme indexes in str that have been matched
        if (last - first >= result.length) return false; // subsequence will have gaps; backtrack
        if (i >= result.length) return true; // all characters are allocated in a subsequence
        let c = result[i];
        let occ = occurrences[c];
        let usedoccurrences = occ.length - available[c];
        for (let j = 0; j <= available[c]; j++) {
            if (dfs(i+1, Math.min(first, occ[j]), Math.max(last, occ[j+usedoccurrences-1]))) {
                return true;
            }
        }
        return false; // backtrack
    })() ? "YES" : "NO"; // immediately invoke dfs: returns a boolean
}

// Test cases
console.log(task18("abcde","L 3 R 2 R 4")); // YES
console.log(task18("linkinpark", "L 6 R 5 L 4")); // YES
console.log(task18("carrace", "L 2 R 2 L 3")); // NO
console.log(task18("pnesumonoultramicroscopicsilicovolcanoconiosisfloccinaucinihilipilification", "R9R1L4L9")); // YES

JS程序按指定幅度按指定方向旋转给定的字符串

JS program to rotate a given String in specified direction by specified magnitude

javascript

string

substring

anagram