Matching Adjacent Words
CJam, 14 13 12 bytes

r$r$.-:)3,-!


Try it online! or verify all test cases at once.

Algorithm

Let s and t be two sorted words of the same length. For s and t to be lexicographically adjacent (LA), it is necessary and sufficient that all pairs of its corresponding characters are also LA.

The condition is clearly sufficient for all words, and necessary for words of length 1.

Now, assume s and t have length n > 1, and let a and b be the first characters, resp., of s and t.

Since s and t are LA, there is some bijective mapping &phi; between the characters of s and the characters of t such that x and &phi;(x) are LA for all x in s, meaning that |x - &phi;(x)| &leq; 1 for all x in s.

Let c = &phi;(a) and d = &phi;-1(b). Because of a's and b's minimality, a &leq; d (1) and b &leq; c (2).

Furthermore, since b and d, and a and c, and LA, d &leq; b + 1 (3) and c &leq; a + 1 (4).

By combining (1) and (3), and (2) and (4), we get that a &leq; d &leq; b + 1 and b &leq; c &leq; a + 1, from which we deduce that a - 1 &leq; b &leq; a + 1 and, therefore, that a and b are LA.

Now, by combining (1) and (4), and (2) and (3), we get that c - 1 &leq; a &leq; d and d - 1 &leq; b &leq; c, from which we deduce that c - 1 &leq; d &leq; c + 1 and, therefore that c and d are LA.

Thus, if we redefine &phi; by &phi;(a) = b and &phi;(d) = c, |x - &phi;(x)| &leq; 1 will still hold for all x in s and, in particular, for all x in s[1:].

This way, s[0] = a and t[0] = b, and s[1:] and t[1:], are LA.

Since s[1:] has length n - 1, this proves the necessity by induction.

Code

r               e# Read the first word from STDIN.
 $              e# Sort its characters.
  r             e# Read the second word from STDIN.
   $            e# Sort its characters.
    .-          e# Perform vectorized subtraction.
                e# This pushes either the difference of char codes of two
                e# corresponding characters or a character that has no does not
                e# correspond to a character in the other, shorter word.
      :)        e# Increment all results.
                e# In particular, this maps [-1 0 1] to [0 1 2].
        3,      e# Push the range [0 1 2].
          -     e# Perform set difference, i.e., remove all occurrences of 0, 1 and
                e# 2 from the array of incremented differences.
           !    e# Apply logical NOT. This gives 1 iff the array was empty iff
                e# all differences gave -1, 0 or 1.