[Challenge] 錯位字遊戲

Beyond Relational TSQL Beginners Challenge 20

Many of you must have played the 'mangled words' game in the school. Here is a challenge that gives you an opportunity to play it once again using TSQL.

Your task is to process the input table that contains several mangled words and try to 'un-mangle' them and validate them against a 'dictionary' table. You might be able to create more than one correct word from some of the input strings. It is also possible that a mangled word is completely incorrect and no valid word can be created from it.

As an example, given "xtet", the valid word that can be formed is "text".

• Sample Data

There are basically two tables.The first table (MangledWord) contains the randomize word list. Sample Input Data for MangledWord table.

ID MangledWord
-- -----------
1  Lnlaheecg
2  etxt

The second one (Dictionary) contains the valid words. Sample Input Data for Dictionary table.

ID Word
-- ---------
1  challenge
2  enigma
3  angle
4  change
5  changing

• Expected Results

ID MangledWord CorrectWords
-- ----------- ----------------------
1  lnlaheecg   angle,challenge,change
2  etxt        No matching word found

• Rules
1. ID should be sorted in Ascending Order.
2. The valid words(if found) will be sorted in Ascending order in the CorrectWords column.
3. If no words can be formed, then the CorrectWords column should contain No matching word found corresponding to the MangledWord.
4. The program should run in SQL SERVER 2005 and above.
5. The output should be in the same way as it has been shown.

• 個人解法

DECLARE @tblMangledWord TABLE(ID INT IDENTITY, MangledWord VARCHAR(100))
INSERT INTO @tblMangledWord 
SELECT 'lnlaheecg' UNION ALL
SELECT 'etxt'

DECLARE @tblDictionary TABLE(ID INT IDENTITY, Word VARCHAR(100))
INSERT INTO @tblDictionary
SELECT 'challenge' UNION ALL
SELECT 'enigma' UNION ALL
SELECT 'angle' UNION ALL
SELECT 'change' UNION ALL
SELECT 'changing'

; 
WITH CTE AS
(
  SELECT 
    ID , 
    MangledWord ,
    LEN(MangledWord)-1 AS Location ,
    SUBSTRING(MangledWord,LEN(MangledWord),1) AS Letter
  FROM @tblMangledWord
  UNION ALL
  SELECT
    ID ,
    MangledWord , 
    Location - 1 ,
    SUBSTRING(MangledWord,Location,1)
  FROM CTE
  WHERE Location > 0
)
, 
CTE2 AS
(
  SELECT 
    ID , 
    Word ,
    LEN(Word) - 1 AS Location ,
    SUBSTRING(Word,LEN(Word),1) AS Letter
  FROM @tblDictionary
  UNION ALL
  SELECT
    ID ,
    Word ,
    Location - 1 ,
    SUBSTRING(Word,Location,1) AS Letter
  FROM CTE2
  WHERE Location > 0
)
,
CTE3 AS
(
  SELECT T3.*
  FROM
    (
      SELECT 
        T1.ID , 
        T1.MangledWord , 
        T2.Word , 
        COUNT(DISTINCT T2.Letter) AS LetterCount
      FROM CTE AS T1 
        JOIN CTE2 AS T2 ON T1.Letter = T2.Letter
      GROUP BY T1.ID , T1.MangledWord , T2.Word
    ) AS T3
    JOIN
    (
      SELECT
        Word , 
        COUNT(DISTINCT Letter) AS LetterCount
      FROM CTE2
      GROUP BY Word 
    ) AS T4 ON T3.Word = T4.Word 
                AND T3.LetterCount = T4.LetterCount
)
SELECT 
  F1.ID , 
  F1.MangledWord , 
  ISNULL(F2.CorrectWords,'No matching word found') AS CorrectWords
FROM @tblMangledWord  AS F1
  LEFT JOIN
    (
      SELECT T5.ID ,
        STUFF
          (
            (
              SELECT ',' + Word
              FROM CTE3 AS T6
              WHERE T5.ID = T6.ID
              ORDER BY Word
              FOR XML PATH('')
            )
            ,1
            ,1
            ,''
          ) AS CorrectWords
      FROM CTE3 AS T5
      GROUP BY ID
    ) AS F2 ON F1.ID = F2.ID

利用 CTE 把兩個 Sample Table 中每個字串的字母都拆出來，兩者進行比對，來判斷是否可以組合成有效單字。

參考資料：
• TSQL Beginners Challenge 20 - Play Mangled Words game in TSQL