函数必须接受两个字符串参数:一个是要旋转的字符串,另一个是表示在某一特定方向上以特定幅度旋转的次数。第二个字符串的形式是......X a X b X c......。X a X b X c......。a,b,c......是整数,表示在其左侧的方向的大小(不超过9)。
例如,如果这些都是参数 。("abcde", "L 3 R 2 R 4")结果为YES。
解释:在这里,旋转次数为3。
因此,在所有的旋转之后,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]);
}
}
};
几个问题。
return
). substring
的第一个参数是字符串,而预期的是数字。count = ans[0];
是把计数从错误的地方。它要从 str2
,不 ans
.str1
但任务是返回 "YES "或 "NO"。简单的部分是旋转。事实上,并不需要真正的旋转。str1
. 只需用索引指向旋转后的字符串的起始点就会更有效率。
困难的部分是要找出构造的字符串是否是 str1
. 困难的是,有些人物在 str1
可能是重复的,所以当你在重复的字母中选择错误的一个时,匹配的尝试可能会失败。这可以通过使用递归和回溯来解决,在重复的字符中尝试使用一个字符,然后再尝试使用下一个字符,直到你成功,或者所有的尝试都失败。
还有一些额外的措施可以改善运行时间:当旋转字符串的旋转次数多于字符数时,在 str1
,你已经可以返回 "NO"。
如果旋转带来的字符串使用的字符多于它在 str1
(因为某个字符位置通过旋转被重新访问),那么也可以返回 "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
这是一个不修改中间字符串的解决方案, 只是跟踪每次旋转后第一个字母的位置.
// 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