overload119
BAN USERJavascript Solution
{{
function getLetterRankWords(str) {
var letterRanks = {};
var alphabet = 'abcdefghijklmnopqrstuvwxyz';
for (var i = 0; i < alphabet.length; i++) {
letterRanks[ i+1 ] = alphabet[i];
}
var results = {};
var gobbleString = function(str, remainingStr, posToConsider) {
if (remainingStr === "") {
results[str] = true;
return;
}
if (posToConsider === 2 && remainingStr.length >= 2) {
// Consider the next two numbers
var nextTwoNum = parseInt( remainingStr[0] + remainingStr[1], 10 );
var letter = letterRanks[ nextTwoNum ];
if (letter) {
gobbleString(str + letter, remainingStr.substring(2), 1);
if (remainingStr.length >= 2) {
gobbleString(str + letter, remainingStr.substring(2), 2);
}
}
} else {
var letter = letterRanks[ parseInt(remainingStr[0], 10) ];
if (letter) {
gobbleString(str + letter, remainingStr.substring(1), 1);
if (remainingStr.length >= 2) {
gobbleString(str + letter, remainingStr.substring(1), 2);
}
}
}
}
gobbleString("", str, 1);
if (str.length >= 2) {
gobbleString("", str, 2);
}
return Object.keys(results);
}
getLetterRankWords('1123');
}}
I'm not entirely sure of the question, in particular, what qualifies as strings to be "swapped" with each other?
Here is an algorithm that finds the largest set of strings based on their length, and it resolves the test case you provided.
var arr = ['mat', 'rat', 'groom', 'broom', 'cat'];
function getSwappable(arr) {
var wordLengths = {};
for (var i = 0; i < arr.length; i++) {
var word = arr[i];
var key = word.length;
if (wordLengths[key]) {
wordLengths[key].push( word );
} else {
wordLengths[key] = [ word ];
}
}
var maxKey = 0;
var maxResult = [];
for (var key in wordLengths) {
if (wordLengths[key].length > maxKey) {
maxKey = wordLengths[key].length;
maxResult = wordLengths[key];
}
}
return maxResult;
}
getSwappable(arr);
Here is a javascript solution that's a bit more readable and extensible, however it is slower than some of the other solutions.
var alphabet = 'smefratdlonikafb';
var BOARD = [];
var BOARD_ROWS = 4;
var BOARD_COLS = 4;
for(var i = 0; i < BOARD_COLS; i++) {
BOARD[i] = [];
for(var j = 0; j < BOARD_ROWS; j++) {
BOARD[i][j] = alphabet[0];
alphabet = alphabet.substring(1);
}
}
function getNearbyCells(x, y) {
var result = [];
if( x < BOARD_COLS-1) {
result.push({ x: x+1, y: y });
if( y < BOARD_ROWS-1 ) {
result.push({ x: x+1, y: y+1 });
}
if( y > 0 ) {
result.push({ x: x+1, y: y-1 });
}
}
if( x > 0 ) {
if( y < BOARD_ROWS-1) {
result.push({ x: x-1, y: y+1 });
}
result.push({ x: x-1, y: y });
if( y > 0 ) {
result.push({ x: x-1, y: y-1 });
}
}
if( y < BOARD_ROWS-1 ) {
result.push({ x: x, y: y+1 });
}
if( y > 0 ) {
result.push({ x: x, y: y-1 });
}
return result;
}
// Returns the location of the letter or false if it could not be found
function findLetter(x, y, l) {
var nearbyCells = getNearbyCells(x, y)
for( var i = 0; i < nearbyCells.length; i++ ) {
var position = nearbyCells[i];
if( BOARD[position.x][position.y] === l ) {
return {
x: position.x,
y: position.y
};
}
}
return false;
}
function searchForWord(x, y, word) {
var l = {x:x, y:y};
for( var i = 0; i < word.length; i++ ) {
var letter = word[i];
l = findLetter(l.x, l.y, letter);
if( !l ) {
return false;
}
}
return true;
}
function hasWord(word) {
// See if the first letter exists by searching the entire board
var firstLetter = word[0];
word = word.substring(1);
var possibleStartLocations = [];
for(var i = 0; i < BOARD_COLS; i++) {
for(var j = 0; j < BOARD_ROWS; j++) {
if(BOARD[i][j] === firstLetter) {
possibleStartLocations.push({
x: i,
y: j
});
}
}
}
// Starting from all the possible start locations, find the word
for( var i = 0; i < possibleStartLocations.length; i++ ) {
var p = possibleStartLocations[i];
var canFindWord = searchForWord(p.x, p.y, word);
if(canFindWord) {
return true;
}
}
return false;
}
- overload119 February 02, 2014